Range Maximum Query

You are given an array of integers, (A), and (Q) queries. For each query, you are provided two indices (L) and (R) (0-indexed). Your task is to determine the maximum element in the subarray (A[L\ldots R]).

Formally, for each query, compute (\max{A[i] \mid L \le i \le R}).

It is recommended to use efficient data structures, such as a segment tree, to process the queries quickly when (A) is large.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains a single 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 (A).
3. The third line contains a single integer (Q) representing the number of queries.
4. Each of the following (Q) lines contains two space-separated integers (L) and (R), representing a query.

outputFormat

For each query, output the maximum element from the subarray (A[L\ldots R]) on a separate line to standard output (stdout).## sample

5
1 3 -2 8 5
3
0 2
1 3
2 4

3
8
8