题目描述

洞窟里有一道长长的通道．它由$\red{N(1≤}$$\red{N≤}$$\red{25000)}$段道尾相连构成，编号分别为$\red{1}$到$\red{N}$．

每个通道有一个阈值，其范围在$\red{[1，}$$\red{10^9]}$依次通过$\red{i..j}$的通道，那奶牛的体重指数就不能超过$\red{i..j}$通道中阈值的最小值．

贝茜有$\red{Q(1≤}$$\red{Q≤}$$\red{25000)}$个问题，想请教你由$\red{i}$到$\red{j}$的通道的阈值的最小值．

输入格式

第$\red{1}$行输入$\red{N}$和$\red{Q，}$

接下来$\red{N}$行输入每个通道的阈值，

之后$\red{Q}$行每行两个整数，对应问题中的$\red{i}$和$\red{j（}$$\red{i<j）}$．

输出格式

对于每个问题，输出其结果．

样例

输入样例

10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10

输出样例

5
38
20
5