Maximum in Subarray Queries

You are given an array of n integers and q queries. For each query, you are required to find the maximum element within a specified subarray of the given array. A query is defined by two integers, L and R, which represent the starting and ending indices (1-indexed) of the subarray.

More formally, for a query with indices L and R, compute:

\(\max\{a_L, a_{L+1}, \dots, a_R\}\)

Your task is to process all the queries and output the maximum value for each one.

Note: The indices provided in the queries are guaranteed to be valid for the given array.

inputFormat

The input is given via standard input (stdin) and has the following format:

1. The first line contains an integer n representing the number of elements in the array.
2. The second line contains n space-separated integers denoting the elements of the array.
3. The third line contains an integer q representing the number of queries.
4. Each of the next q lines contains two space-separated integers L and R representing the bounds of a subarray.

outputFormat

For each query, print the maximum value found in the corresponding subarray on a new line. The output should be written to standard output (stdout).

## sample

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

3
5
5

</p>