Description

Original source: Vijos P1512

Once upon a time, there was a person named W and N and B, who possessed a genius-level memory and collected numerous treasures. After his passing, he left behind a puzzle (specifically designed to test memory!) for future generations. Whoever could easily answer this question would inherit his treasures.

The problem is as follows: You are given a long string of numbers (numbered from $1$ to $N$, and their sizes may vary!). After you have seen them once, they disappear before your eyes, and then the question arises: You are given $M$ queries, each query provides two numbers $A$ and $B$, and you must instantly state the maximum number within the interval from $A$ to $B$.

One day, a beautiful sister flew by from the sky, saw this problem, and found it very interesting (mainly because it was said that the treasure contained a kind of beauty potion that could make this beautiful sister even more charming). So she tried her best to solve this problem. BUT, she failed every time because the number of digits was simply too large! So she asked you, the genius, to help her solve it. If you help her solve this problem, you will receive many sweet rewards!

Input Format

The first line contains an integer $N$ representing the number of digits. The next line contains $N$ numbers. The third line contains an integer $M$, indicating the number of times you will be questioned after seeing the string of numbers. The following $M$ lines each contain two integers $A$ and $B$.

Output Format

Output $M$ lines, each containing a number representing the answer to a query.

Sample 1

6
34 1 8 123 3 2
4
1 2
1 5
3 4
2 3

34
123
123
8

Data Range and Hints

For $30\%$ of the data, $1\le N\le 10^4,1\le M\le 100$;

For $100\%$ of the data, $1\le N\le 2\times 10^5,1\le M\le 10^4$.