Implement a data structure to efficiently calculate the maxima of consecutive array elements.
Input
The first line contains one natural number
N (
\(1 <= N <= 100000\)) — the number of numbers in the array. The second line contains
N numbers from 1 to 100000 — array elements. The third line contains one natural number
K (
\(1 <= K <= 30000\)) &mdash ; the number of requests to calculate the maximum. In the following
K lines, enter two numbers each — the numbers of the left and right elements of the array segment (it is assumed that the elements of the array are numbered from one).
Imprint
For each query, print the value of the maximum element in the specified range of the array. Output the numbers in one line separated by a space.
Examples
| # |
Input |
Output |
| 1 |
5
2 2 2 1 5
2
23
25 |
2 5 |