ישנם $N$ בתים הממוספרים $1, 2, \ldots, N$ על ציר המספרים. בית $i$ ממוקם בקואורדינטה $X_i$. מובטח כי $X_i < X_{i+1}$ עבור כל $i$ ($1 \le i \le N - 1$).

עבור מספרים שלמים $a, b$ המקיימים $1 \le a < b \le N$, נאמר שהבתים העוקבים $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$). מבין כל זוגות המספרים השלמים $(s, t)$ המקיימים $l_i \le s < t \le r_i$ כך שהבתים העוקבים $s, s + 1, \ldots, 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$). מובטח כי $X_i < X_{i+1}$ עבור כל $i$ ($1 \le i \le N - 1$).

השורה השלישית מכילה מספר שלם $Q$, המייצג את מספר השאילתות ($1 \le Q \le 2 \times 10^5$).

כל אחת מ-$Q$ השורות הבאות מכילה שני מספרים שלמים $l_i$ ו-$r_i$, המייצגים את הקצה השמאלי והימני של הטווח המצוין בשאילתה ה-$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