One of the important function, in mathematic and programming languages, is the Maximum function, in its simple form it is take two integers and return the bigger, infact the max.

In this problem we will generalize the function to take a list and two index, and return the max number in this range.

Input

the length of the list N, 0<N<=1000000, followed by N positive integer less than 1000000, one on a line.

a line contain the integer M, the number of query (0<M<=1000000) , the M line each contain two integer i,j (1<=i,j<=N).

Output

print M number, one on a line, the max element between i and j (inclusive)

Example

Input:

5
4 
0 
8 
6
3
1 2
2 4
1 4

Output:
4
8
8