Constant Factor RMQ

This problem is an RMQ (Range Minimum Query) challenge with a twist in constant factor optimization. Given an array of n integers, you are required to answer q queries. Each query consists of two integers l and r (1-indexed) and the answer is the minimum element in the subarray A[l...r].

Efficient constant time query processing is required after an appropriate preprocessing step. Use efficient techniques such as Sparse Table or Segment Tree to pass all given test cases.

inputFormat

The first line of the input contains two integers n and q – the number of elements in the array and the number of queries, respectively.

The second line contains n space-separated integers representing the array elements.

Each of the next q lines contains two integers l and r (1-indexed) specifying the range for an RMQ query.

outputFormat

For each query, output a single line with one integer – the minimum element in the subarray from index l to r (inclusive).

sample

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

1
2
3