Minimum Threshold on Cave Passage

You are given a cave with a long passage comprised of \(N\) segments connected end-to-end, numbered from 1 to \(N\). Each segment \(i\) has a threshold value \(T_i\) where \(1 \le T_i \le 10^9\). When a cow passes through a consecutive group of segments \(i\) to \(j\), its weight index must not exceed the smallest threshold among those segments. You are given \(Q\) queries, and each query consists of two integers \(i\) and \(j\). Your task is to output the minimum threshold value among segments \(i\) to \(j\) (inclusive).

Input constraints:

• \(1 \le N \le 25000\)
• \(1 \le Q \le 25000\)
• Threshold values \(T_i\) are in the range \([1, 10^9]\).

inputFormat

The first line contains two integers \(N\) and \(Q\), denoting the number of segments and the number of queries respectively.

The second line contains \(N\) integers, where the \(i\)-th integer represents the threshold \(T_i\) for the \(i\)-th segment.

Each of the next \(Q\) lines contains two integers \(i\) and \(j\), representing a query to find the minimum threshold in the range from segment \(i\) to segment \(j\) (inclusive).

outputFormat

For each query, output a single line containing the minimum threshold value among the given segments.

sample

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

3
2
4