Maximum Card Value Query

You are given a deck of N cards, where each card has an integer value. You will be given Q queries. Each query specifies two 1-indexed positions, L and R, and your task is to determine the maximum value among the cards in the subarray from position L to R (inclusive).

Input Format: The input begins with an integer N representing the number of cards, followed by N integers denoting the card values. Then an integer Q follows, representing the number of queries. Each of the next Q lines contains two integers, L and R, that represent the range (inclusive) of the subarray for which you should determine the maximum card value.

Example:
For instance, if the cards are [2, 6, 3, 5, 8, 7] and the query is (1, 4), the subarray is [2, 6, 3, 5] and the answer is 6.

Note: All queries are independent.

inputFormat

The first line contains an integer N \( (1 \leq N \leq 10^5) \) representing the number of cards.

The second line contains N space-separated integers \( a_1, a_2, \dots, a_N \) representing the card values.

The third line contains an integer Q \( (1 \leq Q \leq 10^5) \) representing the number of queries.

Each of the following Q lines contains two space-separated integers L and R \( (1 \leq L \leq R \leq N) \) representing a query.

outputFormat

Output Q lines, where the i-th line contains one integer: the maximum value in the subarray from index L to R (inclusive) for the corresponding query.

## sample

6
2 6 3 5 8 7
3
1 4
2 5
3 6

6
8
8

</p>