Terdapat $N$ rumah yang diberi nomor $1, 2, \ldots, N$ pada sebuah garis bilangan. Rumah $i$ terletak pada koordinat $X_i$. Dijamin bahwa $X_i < X_{i+1}$ untuk setiap $i$ ($1 \le i \le N - 1$).

Untuk bilangan bulat $a, b$ dengan $1 \le a < b \le N$, kita katakan bahwa rumah-rumah berurutan $a, a + 1, \ldots, b$ membentuk sebuah interval rumah simetris jika syarat berikut terpenuhi:

• Untuk setiap $i = 0, 1, \ldots, b - a$, berlaku $X_a + X_b = X_{a+i} + X_{b-i}$.

Anda diberikan $Q$ kueri. Proseslah kueri-kueri tersebut secara berurutan.

• Pada kueri ke-$i$, Anda diberikan bilangan bulat $l_i, r_i$ ($1 \le l_i < r_i \le N$). Di antara semua pasangan bilangan bulat $(s, t)$ yang memenuhi $l_i \le s < t \le r_i$ sedemikian sehingga rumah-rumah berurutan $s, s + 1, \ldots, t$ membentuk interval rumah simetris, keluarkan lebar maksimum yang mungkin $X_t - X_s$ dari interval tersebut.

Masukan

Masukan terdiri dari satu kasus uji dengan format berikut:

$$ \begin{aligned} &N \\ &X_1 \ X_2 \ \ldots \ X_N \\ &Q \\ &l_1 \ r_1 \\ &l_2 \ r_2 \\ &\vdots \\ &l_Q \ r_Q \end{aligned} $$

Baris pertama berisi sebuah bilangan bulat $N$, yang menyatakan banyaknya rumah ($2 \le N \le 2 \times 10^5$).

Baris kedua berisi $N$ bilangan bulat $X_1, X_2, \ldots, X_N$, yang menyatakan koordinat rumah-rumah tersebut ($-10^9 \le X_i \le 10^9$). Dijamin bahwa $X_i < X_{i+1}$ untuk setiap $i$ ($1 \le i \le N - 1$).

Baris ketiga berisi sebuah bilangan bulat $Q$, yang menyatakan banyaknya kueri ($1 \le Q \le 2 \times 10^5$).

Masing-masing dari $Q$ baris berikutnya berisi dua bilangan bulat $l_i$ dan $r_i$, yang menyatakan titik ujung kiri dan kanan dari rentang yang ditentukan pada kueri ke-$i$ ($1 \le l_i < r_i \le N$).

Keluaran

Untuk setiap kueri, keluarkan lebar maksimum yang mungkin.

Contoh

Masukan 1

7
-5 -2 0 4 6 9 12
5
1 7
2 6
3 7
4 7
3 6

Keluaran 1

14
8
6
6
4