Triple Jump

This problem is adapted from JOI Open 2019 T1 "Triple Jump".

You are given a road divided into N segments numbered from 1 to N. The i-th segment has a strength of \(A_i\). JOI-kun, a naturally talented sports star, is preparing to perform a triple jump. A triple jump consists of three consecutive jumps, with starting segments denoted by \(a\), \(b\), and \(c\) respectively. These indices must satisfy the following conditions:

• \(a < b < c\).
• The distance of the first jump is at most that of the second jump, i.e. \(b - a \le c - b\) (which can also be written in \(\LaTeX\) as \(2b \le a+c\)).

JOI-kun will perform Q triple jumps. In the \(j\)-th jump, he must choose his starting segments within the interval \([L_j, R_j]\), meaning that \(L_j \le a < b < c \le R_j\). For each triple jump, determine the maximum possible sum of strengths \(A_a + A_b + A_c\) that JOI-kun can achieve with a valid triple of segments. It is guaranteed that the chosen interval always contains at least three segments.

inputFormat

The input is given in the following format:

N
A1 A2 ... AN
Q
L1 R1
L2 R2
...
LQ RQ

Where:

• \(1 \leq N \leq 10^3\) (for the purposes of this problem, assume small constraints).
• Each \(A_i\) is an integer (which may be negative).
• \(1 \leq Q \leq 10^3\).
• For each query, \(1 \leq L_j < R_j \leq N\) and the interval \([L_j, R_j]\) contains at least three segments.

outputFormat

For each query, print the maximum sum of strengths \(A_a + A_b + A_c\) on a separate line.

sample

5
1 2 3 4 5
2
1 5
2 4

12
9