Maximum in Subarray Query

You are given an array of integers and several queries. For each query, which is given as a pair of 1-indexed positions l and r, your task is to compute the maximum value in the subarray from l to r (inclusive). Formally, for each query the answer is given by:

$$\max\{a_l, a_{l+1}, \dots, a_r\}$$

Please read the input from STDIN and output the result for each query on a new line to STDOUT.

inputFormat

The first line contains an integer n, the number of elements in the array. The second line contains n space-separated integers representing the array elements. The third line contains an integer q, the number of queries. The next q lines each contain two space-separated integers l and r, representing the 1-indexed start and end indices of the query.

Example:

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

outputFormat

For each query, output the maximum value found in the subarray from index l to r on a new line.

Example Output:

5
5
5

## sample

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

5
5
5

</p>