Range Maximum Query on Difficulties

You are given a list of problem difficulties and a list of intervals. For each interval, you need to find the maximum difficulty among the problems in that interval. The difficulties are provided in a 1-indexed manner.

Given an array difficulties of N integers and Q queries, each query is a pair of integers \(L\) and \(R\) representing the start and end indices of an interval (1-indexed). For every query, output the maximum value in the subarray \(difficulties[L...R]\).

Example:

Input:
6 3
4 7 2 8 5 9
1 3
2 5
4 6
Output:
7
8
9

</p>

Note: Use 1-indexed positions when reading the intervals. Internally, you may convert them to 0-indexing.)

inputFormat

The first line contains two integers \(N\) and \(Q\): the number of problems and the number of queries.

The second line contains \(N\) integers representing the difficulty of each problem.

The next \(Q\) lines each contain two integers \(L\) and \(R\) (1-indexed), representing an interval. For each query, compute the maximum value in the subarray from \(L\) to \(R\).

Input is read from standard input (stdin).

outputFormat

For each query, output the maximum difficulty on a new line. The results should be printed to standard output (stdout).

## sample

6 3
4 7 2 8 5 9
1 3
2 5
4 6

7
8
9

</p>