Problem Description

There is a long passage in a cave. It is made up of $N$ segments ($1 \leq N \leq 25000$) connected end to end, numbered $1 \ldots N$.

Each segment has a threshold value in the range $[1,10^9]$. If a cow passes through segments $i \ldots j$ in order, then the cow’s weight index must not exceed the minimum threshold among segments $i \ldots j$. Bessie has $Q$ questions ($1 \leq Q \leq 25000$) and wants to ask you for the minimum threshold value from segment $i$ to segment $j$.

Input Format

The first line contains $N$ and $Q$.

The next $N$ lines contain the threshold value of each segment. After that, the next $Q$ lines each contain two integers, corresponding to $i$ and $j$ in the questions ($i < j$).

Output Format

For each query, output the answer.

10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10

5
38
20
5

Hint

Translated by ChatGPT 5