题目描述

本题是一个练习RMQ的题目，单刀直入，给你一个操作：

• $l\ r$ 查询 $[l,r]$ 区间的最大值。

输入格式

第一行两个整数 $n,m$，代表数组元素的个数和操作次数。

第二行是 $n$ 个整数 $x_i$，代表数组元素的初始值。

接下来 $m$ 行，每行有两个整数，$l\ r$。

输出格式

对于每个操作，输出查询区间的最大值。

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

4
2
4
2
3

数据规模

对于所有数据，保证 $1≤n,m≤200000, 1≤l≤r≤n，1≤i≤n，1≤x_i≤10^9$。

前四组数据较小，方便验证正确性，后面数据用于测试时间效率。本题时限不需要用快读快写。