มีบ้าน $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