P5097 [USACO04OPEN] Cave Cows 2

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.

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

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