Range Minimum Query Problem

You are given an array \(A\) of \(n\) integers and \(m\) queries. Each query is specified by two integers \(l\) and \(r\) (1-indexed) and asks you to determine the minimum element in the subarray \(A[l...r]\). To handle a large number of queries efficiently, you are encouraged to preprocess the array (for example, using a Sparse Table) so that each query can be answered in \(O(1)\) time after the preprocessing step.

Input Format: The first line contains two space-separated integers \(n\) and \(m\). The second line contains \(n\) space-separated integers representing the array elements. Each of the following \(m\) lines contains two space-separated integers \(l\) and \(r\), representing the range of the query.

Output Format: For each query, output the minimum value found in the subarray \(A[l...r]\) on a separate line.

Note: The indices are 1-indexed.

inputFormat

The first line of input contains two integers (n) and (m), where (n) is the number of elements in the array, and (m) is the number of queries. The second line contains (n) space-separated integers. Each of the next (m) lines contains two space-separated integers representing the indices (l) and (r) of a query.

outputFormat

For each query, output the minimum value in the subarray from index (l) to (r) (inclusive) on a new line.## sample

8 3
4 2 6 1 7 5 3 8
1 4
2 6
3 8

1
1
1