يوجد $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