You are given an array of n integers that never changes, and q queries. Each query gives positions l and r (1-indexed, inclusive). For each query print the smallest value among positions l to r.
The first line has n and q. The second line has the n values. Each of the next q lines has l and r.
Print the answer to each query on its own line, in order.
1 <= n, q <= 200000 |value| <= 10^9 1 <= l <= r <= n
1000 ms256 MB
8 3 5 2 6 1 7 3 8 4 2 7 1 8 5 5
1 1 7
Positions 2..7 hold 2 6 1 7 3 8 (minimum 1), the whole array has minimum 1, and position 5 alone is 7.
