Maximum Value in Subranges

You are given an integer array \(A\) of size \(n\) and \(q\) queries. Each query is a pair of integers \(l\) and \(r\) (1-indexed) that defines a subrange of the array. Your task is to determine the maximum element in the subarray \(A[l \dots r]\) for each query.

Input details: The first line contains the integer \(n\) (the number of elements in the array). The second line contains \(n\) space-separated integers representing the array. The third line contains an integer \(q\) denoting the number of queries. This is followed by \(q\) lines, each containing two space-separated integers \(l\) and \(r\), indicating the range for that query.

Output details: For each query, print the maximum value in the specified subrange on a new line.

It is guaranteed that the given indices satisfy \(1 \leq l \leq r \leq n\).

inputFormat

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

n
A[0] A[1] ... A[n-1]
q
l1 r1
l2 r2
... 
lq rq

Where:

• \(n\) is the number of elements in the array.
• Each \(A[i]\) is an integer representing the element of the array.
• \(q\) is the number of queries.
• Each query consists of two integers \(l\) and \(r\) representing the subrange of the array (1-indexed).

outputFormat

For each query, output the maximum value in the corresponding subrange. Each result should be printed on a separate line on standard output (stdout).

## sample

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

3
4
5

</p>