题目描述

给定 $n$ 个整数，从 $1$ 到 $n$ 顺序编号。接下来进行 $m$ 次查询，第 $i$ 次查询给出 $a_i,b_i$，请输出第 $a_i$ 个数到第 $b_i$ 个数（包含 $a_i$ 和 $b_i$）之间的最小值。

例如，$n=8$，$8$ 个正整数依次为：$40,20,10,30,70,50,80,60$。若 $m=3$，三次查询分别为：

• $a_1=3,b_1=7$；
• $a_2=1,b_2=2$；
• $a_3=5,b_3=8$。

则：

• 第一次查询，第 $3$ 个数到第 $7$ 个数之间的最小值是 $10$；
• 第二次查询，第 $1$ 个数到第 $2$ 个数之间的最小值是 $20$；
• 第三次查询，第 $5$ 个数到第 $8$ 个数之间的最小值是 $50$。

输入格式

第一行包含两个正整数 $n,m$，分别表示整数的数量及查询次数。

第二行包含 $n$ 个整数，表示给定的序列。

接下来 $m$ 行，每行包含两个整数 $a_i,b_i$，表示一次查询的起始位置和终止位置。

输出格式

输出共 $m$ 行，每行一个整数，表示对应查询区间 $[a_i,b_i]$ 中的最小值。

8 3
40 20 10 30 70 50 80 60
3 7
1 2
5 8

10
20
50

数据范围与提示

• $1 \le n,m \le 10^5$
• 序列中每个整数均满足 $0 \le x \le 10^5$
• $1 \le a_i \le b_i \le n$