Description

区间 $\text{RMQ}$ 问题。

给定一个长度为 $n$ 的序列，$m$ 次询问，求 $\max\{a_l,a_{l+1},...,a_r\}$。

Input Format

第一行两个整数 $n,m$ 分别表示序列大小，询问次数。

第二行 $n$ 个整数表示 $a_i$。

接下来 $m$ 行，每行表示一个操作：l r，求 $\max\{a_l,a_{l+1},...,a_r\}$。

Output Format

共 $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

Hint

$1≤n≤5×10^5,1≤m≤2×10^6,1≤a_i≤10^9$

Source

模板