Background

This is a classic ST table problem — static range maximum.

Please note that the maximum time limit for the largest testdata is only 0.8 s, and the data is not weak. Please ensure that the time complexity per query is $O(1)$. If you use a higher time complexity algorithm, it is not guaranteed to pass.

If you believe your code has the correct time complexity but gets TLE, you can try fast input:

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

The function returns the first integer read.

Fast input is only for speeding up input and is not mandatory.

Problem 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