Description

The old butler is a smart and capable man. He has worked for the master for $10$ full years. To make his accounts clearer, the master requires the butler to record the accounts $k$ times each day. Because the butler is smart and capable, he always keeps the master very satisfied.

However, after some people sowed discord, the master still became suspicious of the butler. So he decided to use a special method to judge the butler’s "loyalty". He numbers each account entry as $1, 2, 3, \ldots$, and from time to time asks the butler questions like: among the entries numbered from $a$ to $b$, what is the minimum amount?

To leave the butler no time to falsify, he always asks multiple questions at once.

Input Format

The first line contains two integers $m, n$, indicating there are $m$ account entries and $n$ queries. The second line contains $m$ numbers, representing the amounts of each account entry. The next $n$ lines each describe a query, with $2$ numbers per line, denoting the starting index $a$ and the ending index $b$.

Output Format

Output the answers to all queries in one line, separated by single spaces.

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

2 3 1

Hint

For $100\%$ of the testdata, $1 \leq m \leq 10^5$, $1 \leq n \leq 10^5$.

Translated by ChatGPT 5