区间最值查询

题目描述

给定一个长度为 $n$ 的序列 $a_i$，并给出 $q$ 次询问，每次询问区间 $[l, r]$，输出序列区间 $a[l...r]$中的最大值。

输入格式

输入包含 $q + 1$ 行： 第一行为2个整数 $n,q$，表示序列长度和询问。 接下来 $q$ 行每行两个整数 $l,r$，表示一组询问。

数据范围

$1\le N\le 10^5,1\le M\le 10^6,1\le X\le Y\le N$。

所有数均不超过int范围。

输出格式

对于每次询问，输出一个整数表示答案，占一行。

样例 #1

样例输入 #1

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

样例输出 #1

5 
8