Gấu đang thi nhảy trên một con đường rất dài gồm ~N~ chặng được đánh số từ ~1~ đến ~N~. Khi đến chặng ~i~, Gấu sẽ được điểm thưởng là ~A_i~. Để chuẩn bị thật tốt cho kì thi, Gấu quyết định sẽ tập nhảy trong ~Q~ ngày, mỗi ngày Gấu chỉ nhảy đúng ba chặng là ~x, y, z~ thuộc đoạn ~[L, R]~ sao cho thỏa các điều kiện:

• ~L \leq x < y < z \leq R~.
• ~y - x \leq z - y~.
• ~A_x + A_y + A_z \max~.

Hãy giúp Gấu in ra điểm thưởng lớn nhất anh ấy có thể đạt được trong ~Q~ ngày nhé.

Dữ liệu vào

• Dòng đầu gồm số nguyên ~N~ ~(1 \leq N \leq 5*10^5)~.
• Dòng hai chứa ~N~ số nguyên dương ~A_i~ ~(1 \leq A_i \leq 10^9)~.
• Dòng ba gồm số nguyên ~Q~ ~(1 \leq Q \leq 5*10^5)~.
• ~Q~ dòng sau, mỗi dòng gồm hai số nguyên ~L, R~ ~(1 \leq L \leq R \leq N)~.

Dữ liệu ra

Gồm ~Q~ dòng, mỗi dòng là đáp án cho ngày thứ ~i~.

Ví dụ

Input

5
1 5 3 4 5
2
1 5
1 3

Output

13
9

Note

• Ở ngày đầu tiên, chọn ~(x, y, z) = (2, 3, 5)~.
• Ở ngày thứ hai, chọn ~(x, y, z) = (1, 2, 3)~.

Tính điểm

• Subtask 1 (5 điểm): ~1 \leq N, Q \leq 100~.
• Subtask 2 (14 điểm): ~1 \leq N \leq 5000~.
• Subtask 3 (27 điểm): ~1 \leq N \leq 2*10^5, Q = 1, L_1 = 1, R_1 = N~.
• Subtask 4 (54 điểm): Không có ràng buộc gì thêm.