Maximum Sales in Ranges

You are given an array \(S\) of \(n\) integers representing sales values, indexed from \(0\) to \(n-1\). You are also provided \(q\) queries, where each query is represented as a pair \((L, R)\). For each query, compute the maximum sales value in the subarray from index \(L\) to index \(R\) (inclusive).

Input: The input consists of an integer \(n\) (the number of sales entries), followed by \(n\) space-separated integers denoting the sales values. Next, an integer \(q\) represents the number of queries, followed by \(q\) lines each containing two space-separated integers \(L\) and \(R\) (0-indexed).

Output: For each query, output a single line containing the maximum sales value in the queried range.

inputFormat

The first line contains a single integer n, the number of sales entries. The second line contains n space-separated integers representing the sales values. The third line contains a single integer q, the number of queries. Each of the following q lines contains two space-separated integers L and R (0-indexed), indicating a query.

outputFormat

For each query, output one line containing the maximum sales value found in the range from L to R (inclusive).## sample

6
5 3 8 9 2 4
3
1 4
0 5
2 3

9
9
9