You are given an array
A [1…N]. It is required to perform
M calculation of the minimum element on the segment from
L to
R.
Input
The first line contains the number
N (
\(1 <= N <= 100000\)) – array size. The second line contains
N numbers – array elements. The third line contains the number
M (
\(1 <= M <= 100000\)) – minimum number of requests. The next
M lines contain pairs of numbers
L and
R (
\(L <= R < = N\)) describing segments.
Imprint
For each query print the value of the minimum on the segment separated by a space.
Examples
| # |
Input |
Output |
| 1 |
5
3 1 8 7 9
2
1 3
3 5
| 1 7 |