Range Minimum Query

You are given $N$ integers $a_0, a_1, \dots , a_{N-1}$. You then have to answer $Q$ queries. For each one, you are given two number $l$ and $r$, and should answer with the smallest number among $a_l,a_{l+1},\dots ,a_{r}$.

Input

The first line contains two integers $N$ and $Q$ ($1 \leq N \leq 4 \cdot 10^5$, $1 \leq Q \leq 4 \cdot 10^5$), the number of integers and the number of queries.

The next line contains the $N$ integers $a_0, a_1, \dots , a_{N-1}$ ($1 \leq a_i \leq 4 \cdot 10^5$).

The following $Q$ lines describe one question each. Each line contains two integers $l$ and $r$ ($0 \leq l \leq r \leq N-1$), the endpoints of the query.

Output

Print the answer to each question in the same order as the input: the smallest number among $a_l, a_{l+1},\dots ,a_{r}$.

5 3
5 1 2 3 1
0 2
0 0
2 3

1
5
2