题目描述

输入一串数字，给定$M$个询问，每次询问就给你两个数字$X, Y$，要求你说出$X$到$Y$这段区间内的最大数。

样例输入

第一行两个整数$N, M$表示数字的个数和要询问的次数

接下来一行为$N$个数字

接下来$M$行，每行都有两个整数$X, Y$

样例输出

输出总共$M$行，每行输出一个数

样例

样例一

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

5
8

数据范围

对于全部数据

$1 \le N \le 10^{5}, 1 \le M \le 10^{6}, 1 \le X \le Y \le N$

数据不超过$C/C++$的$int$范围