Efficient Range Minimum Queries

You are given an array of N integers and Q queries. For each query, you need to find the minimum element in a given subarray defined by two indices L and R (1-indexed). To achieve efficient querying, you are required to preprocess the array using a Sparse Table data structure so that each query can be answered in O(1) time after O(NlogN) preprocessing.

Mathematical Formula:

The key idea is to utilize the following formula for answering a query on the range [L, R]:

[ \min { a[L], a[L+1], \ldots, a[R] } = \min \Big( st[L][j],, st[R - 2^j + 1][j] \Big) ]

where ( j = \lfloor \log_2(R-L+1) \rfloor ).

inputFormat

The input is read from stdin and consists of:

• The first line contains two space-separated integers, N (the number of elements in the array) and Q (the number of queries).
• The second line contains N space-separated integers representing the array elements.
• Then follow Q lines, each containing two space-separated integers L and R (1-indexed) that represent the range of the query.

outputFormat

For each query, output the minimum element in the subarray from index L to R (inclusive) on a new line to stdout.

## sample

5 3
1 2 3 4 5
1 3
2 4
3 5

1
2
3

</p>