Taco Temperature Queries

You are given an array of temperature readings for a corridor with n rooms. Your task is to answer range maximum queries efficiently by preprocessing the temperature readings using a sparse table. The sparse table is built in (O(n \log n)) time and each query is answered in (O(1)) time. In mathematical terms, you must construct a table (st) such that the number of columns is (k = \lfloor \log_2 n \rfloor + 1). For each query defined by two indices (l) and (r) (1-indexed), output the maximum temperature in that segment.

inputFormat

The first line of input contains a single integer (n) representing the number of rooms. The second line contains (n) space-separated integers representing the temperature readings. 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) (1-indexed), representing a query for the maximum temperature in the interval [l, r].

outputFormat

For each query, output the maximum temperature in the given range on a new line.## sample

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

3
4
5