ST 表 & RMQ 问题

• 时间限制：1 秒
• 内存限制：128 MiB

题目描述

给定一个长度为 $N$ 的数列和 $M$ 次询问。对于每次询问，求指定闭区间内所有数的最大值。

输入格式

第一行包含两个整数 $N,M$，分别表示数列长度和询问次数。

第二行包含 $N$ 个整数 $a_1,a_2,\ldots,a_N$。

接下来 $M$ 行，每行包含两个整数 $l_i,r_i$，表示询问闭区间 $[l_i,r_i]$。

输出格式

输出 $M$ 行。第 $i$ 行输出第 $i$ 次询问区间中的最大值。

样例输入 1

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

样例输出 1

9
9
7
7
9
8
7
9

数据范围

对于所有数据，$1\le N\le 10^5$，$1\le M\le 2\times 10^6$，$0\le a_i\le 10^9$，$1\le l_i\le r_i\le N$。