Module: SPARSE TABLE


Problem

1 /2


Minimum on segment of immutable array

Theory Click to read/hide

Error

Problem

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