《传奇人物大爷传记》之大爷找宝藏(2)

题目背景

大爷在你的帮助下成功通过了门，但没想到后面还有一扇门，上面刻着一幅壁画…………

壁画中似乎画着古人在解数学题的情景…………

第一行有一串数字（这显然是题干）

下面有N个“数对”（这显然是问题）

下面有一行字（这显然是提示），凭着大爷托班毕业的语文水平，他也是毫不费力就看了出来…………

第一行两个整数n,m，分别表示第一行数字的个数和问题的个数。

接下来一行是n个数字（描述中的“第一行的数字”）。

最后是m行，每行2个整数x,y,表示要在一串数字中求x到y这段区间内的最大数。

输出共m行，表示问题的答案。

3
5

10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8

5
8

对于10%的数据，$1\le n \le 10,1\le m \le 10$

对于30%的数据，$1\le n \le 1000,1\le m \le 100$

对于50%的数据，$1\le n \le 1000,1\le m \le 10^4$

对于80%的数据，$1\le n \le 10^4,1\le m \le 10^5$

对于100%的数据，$1\le n \le 10^5,1\le m \le 10^6,1\le x,y \le n$