Bob's Average

Bob came up with a new way to compute the average of an array with an odd number of elements. While the length of the array is greater than one, the following operation is performed: an arbitrary segment of length 3 with boundaries $l$ and $r = l + 2$ is selected, the median of these three elements is computed, and the three elements are replaced by one element equal to the median. The median of three elements is the second-largest of them. For example, the median of $[1, 5, 4]$ is $4$, and the median of $[2, 2, 2]$ is $2$.

For the array $[4, 1, 3, 2, 5]$, choose $l = 2$, $r = 4$. The median of $[1, 3, 2]$ is $2$, so the array becomes $[4, 2, 5]$. Then choose $l = 1$, $r = 3$. The median of $[4, 2, 5]$ is $4$, so the array becomes $[4]$.

The result depends on the choice of segments. Bob chooses the segments so that the single number left at the end is as large as possible. This number is called Bob's average for the array.

For an array $a$ of $n$ elements, you must answer $q$ queries. The $j$-th query gives $L_j$ and $R_j$, and the answer is Bob's average of the subarray $[a_{L_j}, a_{L_j+1}, \ldots, a_{R_j}]$. Every query has an odd segment length.

The first line contains an integer $n$ ($3 \leq n \leq 5 \cdot 10^4$), the size of the array.

The second line contains $n$ integers $a_i$ ($0 \leq a_i \leq 10^9$), the array elements.

The third line contains an integer $q$ ($1 \leq q \leq 10^5$), the number of queries.

Each of the next $q$ lines contains two integers $L_j$ and $R_j$ ($1 \leq L_j \leq R_j \leq n$). It is guaranteed that $R_j - L_j + 1$ is odd.

For each query, print on its own line the answer to that query, a single integer.