Minimum value

You are given $N$ integers in order ($1 \le N \le 100{,}000$). Finding the smallest value from the $a$-th integer through the $b$-th integer is not hard. It becomes a harder problem once $M$ such pairs $a$, $b$ are given ($1 \le M \le 100{,}000$). Solve it.

Here the $a$-th means the $a$-th in input order. For example, if $a = 1$ and $b = 3$, find the minimum among the 1st, 2nd and 3rd integers in input order. Each integer is between 1 and 1,000,000,000.

The first line contains $N$ and $M$. Each of the next $N$ lines contains one integer. Each of the following $M$ lines contains $a$ and $b$ separated by a space ($1 \le a \le b \le N$).

Print the answer for each $a$, $b$ on its own line, in the order the pairs were read, for a total of $M$ lines.