Background

区间最小值

题目描述：

给定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, b3 = 8

第一次查询：第3个数（10）到第7个数（80）之间最小值是10；

第二次查询：第1个数（40）到第2个数（20）之间最小值是20；

第三次查询：第5个数（70）到第8个数（60）之间最小值是50；

故输出

10

20

50。

输入描述：

第一行输入两个整数n和m(1≤n，m≤10 5)，分别表示整数的数量及查询次数

第二行输入n个整数（0≤整数≤105）

接下来m行，每行输入2个整数ai和bi（1≤ai≤bi≤n），分别表示查询的起始位置和终止位置

输出描述：

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

样例输入：

8 3

40 20 10 30 70 50 80 60

3 7

1 2

5 8

样例输出：

10

20

50

Limitation

1s, 1024KiB for each test case.