Range Max Query - Speedrun Mode

Description

Luogu P3865. Given a sequence with $n$ integers, you need to query the max value in range $[l,r]$. It's $1$ indexed。

Input & Output

The first line has two integers $n,m$, represents the size of the sequence, the number of queries. The next $m$ lines each contains two integers $l,r$, you need to output the max element in range $[l,r]$.

Samples

input #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

9
9
7
7
9
8
7
9

Constraints

$1 \leq l \leq r \leq n \leq 100000$, $1 \leq m \leq 2\times 10^6$, the value of each element is in range $[0,10^9].$

Time Limit: 3.0s   |   Memory Limit: 256 MB