Range Maximum Query

You are given a sequence of \( N \) integers and \( M \) queries. For each query, you need to find the maximum value in the specified interval of the sequence.

The problem can be formally defined as follows:

Given a sequence \( a_1, a_2, \ldots, a_N \) and \( M \) queries. For each query, given two indices \( L \) and \( R \) (1-indexed), output \( \max\{a_L, a_{L+1}, \ldots, a_R\} \).

inputFormat

The first line contains two integers \( N \) and \( M \), representing the length of the sequence and the number of queries respectively.

The second line contains \( N \) integers representing the sequence.

Each of the following \( M \) lines contains two integers \( L \) and \( R \) (1-indexed), representing a query.

outputFormat

For each query, output a single line containing the maximum value in the specified interval.

sample

5 3
1 2 3 2 1
1 3
2 4
1 5

3
3
3