题目描述

给你 $n$ 个数，再给你 $q$ 次询问，每次询问一个区间 $[l,r]$，求这个区间的最大值。

输入格式

第一行两个整数 $n$，$q$，表示数字的个数以及询问的个数。 第二行 $n$ 个整数，第 $i$ 个整数为 $a_i$。 接下来 $q$ 行，每行两个整数 $l,r$，表示每一次询问

输出格式

输出 $q$ 行，表示每次询问的答案。

样例 1

样例输入 1

5 5
1 7 2 5 8
1 3
2 4
3 5
1 5
3 4

样例输出 1

7
7
8
8
5

样例 2

样例输入 2

6 4
1 1 4 5 1 4
1 6
1 4
1 3
4 6

样例输出 2

5
5
4
5