Сан осінде $1, 2, \ldots, N$ сандарымен нөмірленген $N$ үй бар. $i$-ші үй $X_i$ координатасында орналасқан. Әрбір $i$ ($1 \le i \le N - 1$) үшін $X_i < X_{i+1}$ екеніне кепілдік беріледі.

$1 \le a < b \le N$ шартын қанағаттандыратын $a, b$ бүтін сандары үшін, егер келесі шарт орындалса, қатар орналасқан $a, a + 1, \ldots, b$ үйлері үйлердің симметриялы аралығын құрайды деп айтамыз:

• Әрбір $i = 0, 1, \ldots, b - a$ үшін $X_a + X_b = X_{a+i} + X_{b-i}$ теңдігі орындалады.

Сізге $Q$ сұратым берілген. Оларды ретімен өңдеңіз.

• $i$-ші сұратымда сізге $l_i, r_i$ ($1 \le l_i < r_i \le N$) бүтін сандары беріледі. $l_i \le s < t \le r_i$ шартын қанағаттандыратын және қатар орналасқан $s, s + 1, \ldots, t$ үйлері үйлердің симметриялы аралығын құрайтындай барлық $(s, t)$ бүтін сандар жұптарының ішінен аралықтың мүмкін болатын ең үлкен $X_t - X_s$ енін шығарыңыз.

Кіріс деректер

Кіріс деректер келесі форматтағы бір тест жағдайынан тұрады:

$$ \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} $$

Бірінші жолда үйлердің санын білдіретін бір бүтін сан $N$ берілген ($2 \le N \le 2 \times 10^5$).

Екінші жолда үйлердің координаталарын білдіретін $N$ бүтін сан $X_1, X_2, \ldots, X_N$ берілген ($-10^9 \le X_i \le 10^9$). Әрбір $i$ ($1 \le i \le N - 1$) үшін $X_i < X_{i+1}$ екеніне кепілдік беріледі.

Үшінші жолда сұратымдар санын білдіретін бір бүтін сан $Q$ берілген ($1 \le Q \le 2 \times 10^5$).

Келесі $Q$ жолдың әрқайсысында $i$-ші сұратымда көрсетілген ауқымның сол және оң жақ шеткі нүктелерін білдіретін екі бүтін сан $l_i$ және $r_i$ берілген ($1 \le l_i < r_i \le N$).

Шығыс деректер

Әрбір сұратым үшін мүмкін болатын ең үлкен енді шығарыңыз.

Мысалдар

Кіріс деректер 1

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

Шығыс деректер 1

14
8
6
6
4