P5097 [USACO04OPEN] Cave Cows 2

题目描述

洞窟里有一道长长的通道．它由 $N$ ( $1 \leq N \leq 25000$ )段道尾相连构成，编号分别为 $1 \ldots N$ 。

每个通道有一个阈值，其范围在 $[1,10^9]$ 。依次通过 $i \ldots j$ 的通道，那奶牛的体重指数就不能超过 $i \ldots j$ 通道中阈值的最小值。贝茜有 $Q$ ( $1 \leq Q \leq 25000$ )个问题，想请教你由 $i$ 到 $j$ 的通道的阈值的最小值。

输入格式

第1行输入 $N$ 和 $Q$ 。

接下来 $N$ 行输入每个通道的阈值，之后 $Q$ 行每行两个整数，对应问题中的 $i$ 和 $j$（ $i<j$ ）。

输出格式

对于每个问题，输出其结果。

输入输出样例 #1

输入 #1

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

输出 #1

5
38
20
5