Cave Cows 2      cavecow2.X

In one cave Bessie is planning to explore, a long corridor is made up of N
segments (1 <= N <= 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 <= Q <= 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.

PROBLEM NAME: cavecow2

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 2 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.

SAMPLE INPUT:

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

OUTPUT FORMAT:

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

SAMPLE OUTPUT:

5
38
20
5