Tallest Book Heights Query

You are given a collection of books and their respective heights. For a set of queries, each query provides two integers (L) and (R) (using 1-indexed positions) and your task is to determine the height of the tallest book in the interval (L) to (R). In other words, for each query, you should compute [ \max_{i=L}^{R}(h_i), ] where (h_i) is the height of the (i^{th}) book. Ensure that your program processes input from standard input (stdin) and outputs the result to standard output (stdout) exactly as specified.

inputFormat

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

1. The first line contains an integer (n) representing the number of books.
2. The second line contains (n) space-separated integers representing the heights of the books.
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) (with (1 \le L \le R \le n)), representing a query.

outputFormat

For each query, print the height of the tallest book in the range from (L) to (R). Each answer should be printed on a separate line, in the order of the queries.## sample

5
5 2 9 4 7
3
1 3
2 5
1 5

9
9
9