4225 - 第七课: 静态区间最小值查询

给定一个长度为n的数组$a_0, a_1, a_2, ..., a_{n-1} $。

有m个询问$(x,y)(0 \le x \le y \lt n)$,对于每一个询问,求$a_x, a_{x+1},..., a_{y-1}, a_y$这些数字中的最小值是多少。

输入

第一行给出两个整数,$ n(1 \le n \le 10^5), m(1 \le m \le 10^5) $。

接下来一行给出n个整数$a_0, a_1, a_2, ..., a_{n-1}(0 \le a_i \le 10^9)$。

接下来m行,每行给出两个整数$(x,y)(0 \le x \le y \lt n)$。

输出

对于每一个询问,输出一个整数,表示最小值。

样例

输入

8 3
1 3 10 30 5 3 6 7
0 0
0 7
2 3

输出

1
1
10
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题