Range Minimum Query (RMQ) is a set of problems which deals with finding a property (here minimum) of a range. Segment Tree can be very helpful when solving with such problems. A segment tree is a tree like data structure which is used to store the information about intervals. Here's the [(wiki link)] of it.
You are given a array of N integers, arr, arr, .., arr[(N-1)]. And you are given a list of ranges. For each range, (l, r) you have to find the minimum value between range arr[l], arr[l+1], arr[l+2], .., arr[r].
First line will contain two integers, N M, length of array and number of queries. Then in next line, there are N space separated integers which represent the array, arr, arr, .., arr[N-1]. Then M line follows. Each M line will contain two integers, l r, representing a range.
For each range, (l, r), you have to print the minimum integer in subarray arr[l], arr[l+1], .., arr[r] in separate line.
Constraints 1 <= N, M <= 105 -105 <= arr[i] <= 105 , where 0 <= i < N 0 <= l <= r < N