背景

曾几时，小 X 在 AK 某场比赛时得到 CBH 的指教，影响至今。

题目描述

给出一个长度为 $n$ 的序列 $A$，

有 $m$ 次询问，每次给出 $l$,$r$。求出从 $l$ 到 $r$ 这个区间的最大值(包括端点)。

输入格式

第一行是 $n$,$m$ 两个正整数

第二行是 $n$ 个正整数，表示 $A$ 序列

接下来的 $m$ 行，每行有两个正整数 $l$，$r$

输出格式

有 $m$ 行最大值输出

样例

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

6
2
9

数据范围

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

对于 $50\%$ 的数据，$n/1.5\le r-l$

对于 $100\%$ 的数据，$1\le n\le 2\times 10^3$，$1\le m\le 4\times 10^5$，$0\le a_i\le 2^{31}-1$，$1\le l\le r\le n$

后记

那一次小 X 确实 AK 了比赛，但是并不是第一个，因为比赛的缓冲池冲爆了。