题目描述

给出一个长度为 $n$ 的整数序列，回答 $m$ 次询问，每次询问区间 $[l,r]$ 内所有数的最大值。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数。

接下来 $m$ 行，每行两个整数 $l,r$，表示一次询问。

输出格式

输出 $m$ 行，每行一个整数，表示对应询问的答案。

输入输出样例 #1

输入 #1

5 3
1 5 3 2 4
1 3
2 5
1 5

输出 #1

5
5
5

说明

数据范围

• 对于 $100\%$ 的数据，$1\le l\le r\le n\le 10^5$，$m\le 10^5$，$|a_i|\le 10^9$。