Description

给定n个整数，从1到n顺序编号，接下来进行m次查询，第i次查询第ai个数到第bi个数(包含ai和bi)之间的最小值并输出。 例如:n=8，8个正整数依次为: 40 20 10 30 70 50 80 60 m= 3，3次查询分别为: a1 = 3，b1 = 7 a2 = 1，b2 = 2 a3 = 5，bs = 8 第一次查询:第3个数(10)到第7个数(80)之间最小值是10; 第二次查询:第1个数(40)到第2个数(20之间最小值是20; 第三次查询:第5个数(70)到第8个数(60)之间最小值是50; 故输出 10 20 50

Input Format

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

Output Format

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

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

10
20
50