Problem Description

In one cave Bessie is planning to explore, a long corridor is made up of $N$ segments ($1 \le N \le 25,000$ and numbered $1..N$) joined end-to-end.
Each of these segments has a particular width which can only be traversed by a cow whose "fatness" index is no larger than that width.
A cow can travel along a sequence $i..j$ of these segments only if its fatness index is no larger than the minimum width of all of those corridors. Corridor widths are integers in the range $1..1,000,000,000$.

In order to plan her caving expedition, Bessie needs to answer a collection of $Q$ ($1 \le Q \le 25,000$) queries of the form "what is the maximum fatness of a cow that can pass through the sequence $i..j$ of corridors?". Please help Bessie with her dilemma.

Input Format

• Line $1$: Two space-separated integers, $N$ and $Q$.

• Lines $2..N+1$: Each line gives the integer width of a corridor. Line $2$ describes corridor $1$; line $3$ describes corridor $2$; and so on.

• Lines $N+2..N+Q+1$: Each line corresponds to a query and contains two space-separated integers $i$ and $j$ (where $i < j$), giving the indices of the corridors at both ends of the query interval.

Output Format

• Lines $1..Q$: Each line contains the integer answer to a query.

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

5
38
20
5