J3 例题-7 区间最大值

题目描述

给定一个长度为 $N$ 的数列，和 $M$ 次询问，求出每一次询问的区间内数字的最大值。

输入格式

第一行包含两个整数 $N,M$，分别表示数列的长度和询问的个数。 第二行包含 $N$ 个整数 $a_i$ ，依次表示数列的第 $i$ 项。 接下来 $M$ 行，每行包含两个整数 $l_i,r_i$，表示查询的区间为 $[l_i,r_i]$ 。

输出格式

输出包含 $M$ 行，每行一个整数，依次表示每一次询问的结果。

样例输入

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

样例输出

9
9
7
7
9
8
7
9

样例说明

无

数据范围

对于 $30\%$ 的数据，满足 $1\leq N,M\leq 10$。 对于 $70\%$ 的数据，满足 $1\leq N,M\leq 10^5$。 对于 $100\%$ 的数据，满足 $1\leq N\leq 10^5,1\leq M\leq 2\times 10^6,a_i \in [0,10^9],1\leq l_i\leq r_i\leq N$。