Có một con đường thẳng rất dài gồm \(N\) đoạn có độ dài bằng nhau, được đánh số từ \(1\) đến \(N\). Độ cứng của đoạn thứ \(i\) là \(A_i\).

JOI-kun, một ngôi sao thể thao tài năng, sẽ thực hiện môn nhảy ba bước. Mỗi lần nhảy ba bước gồm ba bước nhảy liên tiếp. Gọi \(a,b,c\) là số hiệu các đoạn đường mà JOI-kun giậm nhảy. Các số này phải thỏa mãn:

• \(a<b<c\): số hiệu các đoạn đường tăng dần.
• \(b-a\le c-b\): độ dài bước nhảy thứ nhất không lớn hơn độ dài bước nhảy thứ hai.

JOI-kun sẽ thực hiện \(Q\) lần nhảy ba bước. Trong lần thứ \(j\), các đoạn giậm nhảy phải có số hiệu từ \(L_j\) đến \(R_j\), tức là \(L_j\le a<b<c\le R_j\).

JOI-kun muốn giậm nhảy trên các đoạn đường cứng hơn. Với mỗi lần nhảy, hãy tính tổng độ cứng lớn nhất của ba đoạn giậm nhảy.

Dữ liệu vào

Dữ liệu được đọc từ đầu vào chuẩn. Tất cả các giá trị đều là số nguyên.

• Dòng đầu chứa \(N\).
• Dòng thứ hai chứa \(A_1,A_2,\ldots,A_N\).
• Dòng thứ ba chứa \(Q\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(j\) chứa \(L_j,R_j\).

Dữ liệu ra

Ghi \(Q\) dòng ra đầu ra chuẩn. Dòng thứ \(j\) chứa tổng độ cứng lớn nhất của ba đoạn giậm nhảy trong lần nhảy thứ \(j\).

Ràng buộc

• \(3\le N\le 500\,000\).
• \(1\le A_i\le 100\,000\,000\) với \(1\le i\le N\).
• \(1\le Q\le 500\,000\).
• \(1\le L_j<L_j+2\le R_j\le N\) với \(1\le j\le Q\).

Phân nhóm

1. \(5\) điểm: \(N\le 100\), \(Q\le 100\).
2. \(14\) điểm: \(N\le 5\,000\).
3. \(27\) điểm: \(N\le 200\,000\), \(Q=1\), \(L_1=1\), \(R_1=N\).
4. \(54\) điểm: Không có ràng buộc bổ sung.

Ví dụ

5
5 2 1 5 3
3
1 4
2 5
1 5

12
9
12

5
5 4 4 5 4
1
1 5

14

15
12 96 100 61 54 66 37 34 58 21 21 1 13 50 81
12
1 15
3 12
11 14
1 13
5 9
4 6
6 14
2 5
4 15
1 7
1 10
8 13

277
227
72
262
178
181
174
257
208
262
262
113

Nguồn

JOI Open Contest 2019, bài Triple Jump (jumps), ngày 14/7/2019. Bản dịch từ đề tiếng Anh chính thức của JCIOI, theo giấy phép CC BY-SA 4.0.