Description

Given a sequence of numbers, you will receive $M$ queries. Each query provides two numbers $X$ and $Y$, and you need to determine the maximum number in the interval from $X$ to $Y$.

Input Format

The first line contains two integers $N$ and $M$, representing the number of elements and the number of queries, respectively.
The next line contains $N$ numbers.
The following $M$ lines each contain two integers $X$ and $Y$.

Output Format

Output $M$ lines, each containing the answer to the corresponding query.

Sample 1

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

5
8

Constraints and Hints

For all data, $1\le N\le 10^5$, $1\le M\le 10^6$, $1\le X\le Y\le N$. The numbers do not exceed the int range in C/C++.