Description

Given a sequence of length $N$ and $M$ queries, for each query, find the maximum number in the specified interval.

Input Format

The first line contains two integers $N, M$, representing the length of the sequence and the number of queries.

The second line contains $N$ integers (denoted as $a_i$), representing the $i$-th element of the sequence in order.

The next $M$ lines each contain two integers $l_i, r_i$, indicating that the query interval is $[l_i, r_i]$.

Output Format

Output $M$ lines, each containing one integer, representing the answer to each query in order.

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

• For 30% of the testdata, $1 \le N, M \le 10$.
• For 70% of the testdata, $1 \le N, M \le {10}^5$.
• For 100% of the testdata, $1 \le N \le {10}^5$, $1 \le M \le 2 \times {10}^6$, $a_i \in [0, {10}^9]$, $1 \le l_i \le r_i \le N$.

Translated by ChatGPT 5