编程实现

给定 $n$ 个整数，从 $1$ 到 $n$ 顺序编号，接下来进行 $m$ 次查询，第 $i$ 次查询第 $a_i$ 个数到第 $b_i$ 个数(包含 $a$ 和 $b$)之间的最小值并输出。 例如：$n=8$，$8$ 个正整数依次为：$40$ $20$ $10$ $30$ $70$ $50$ $80$ $60$ $m = 3$，$3$ 次查询分别为： $a_1=3，b_1=7$ $a_2=1，b_2=2$ $a_3=5，b_3=8$ 第一次查询：第 $3$ 个数 $(10)$ 到第 $7$ 个数 $(80)$ 之间最小值是 $10$； 第二次查询：第 $1$ 个数 $(40)$ 到第 $2$ 个数 $(20)$ 之间最小值是 $20$； 第三次查询：第 $5$ 个数 $(70)$ 到第 $8$ 个数 $(60)$ 之间最小值是 $50$； 故输出： $10$ $20$ $50$

输入描述

第一行输入两个整数 $n$ 和 $m(1≤n，m≤100000)$，分别表示整数的数量及查询次数； 第二行输入 $n$ 个整数($0≤$ 整数$≤10^5$) 接下来 $m$ 行，每行输入 $2$ 个整数 $a_i$ 和 $b_i(1≤a_i≤b_i≤100000)$，分别表示查询的起始位置和终止位置

输出描述

输出共 $m$ 行，每行输出一个整数，分别表示每次查询得到的第 $a_i$ 个数到第 $b_i$ 个数之间(包含 $a_i$ 和 $b_i$)的最小值并输出。

样例

输入样例 #1

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

输出样例 #1

10 
20 
50