Description

Moreover, loidc has a special ability: he can foresee the future and accurately guess how many gold medals the Chinese team will win in any single unit of time. However, the workload is huge, and predicting gold medals consumes a lot of energy, so he cannot accurately determine which unit time within a given interval attains the maximum number of gold medals. This makes loidc quite upset. After thinking for a while, he thought of you, because he knows you are an OIer. He chuckled and handed the problem over to you. loidc hopes you can produce the answer within 1 s.

Description

Input Format

The first line contains an $n$, indicating there are $n$ time intervals.

The next line contains $n$ numbers $a_i$, where $a_i$ denotes the number of gold medals loidc predicts the Chinese team will win in the $i$-th time interval.

Then, the third line contains a number $m$, indicating loidc has $m$ queries.

The next $m$ lines each contain two numbers $x_i$ and $y_i$, asking which unit time within the interval $[x_i, y_i]$ has the maximum number of gold medals.

loidc has a habit of asking questions in order; that is, each query is asked after the previous one.

Note that for the $i$-th and $(i+1)$-th queries, it strictly holds that $x_i \le x_{i+1}$ and $y_i \le y_{i+1}$.

Output Format

Output $m$ lines. Each line contains a single $k_i$, denoting the answer to the $i$-th query.

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

1
2
3
4
5

Hint

$30\%$: $n \le 1000$, $m \le 1000$.

$100\%$: $n \le {10}^5$, $m \le {10}^5$.

All other input and output values are less than maxlongint.

The testdata guarantees $a_i$ are all distinct.

Translated by ChatGPT 5