The Faithful Butler

The wealthy master employed a very capable butler for 10 years. Every day, the butler was required to record the accounts k times so that the master could have a clear record of his finances. The records were sequentially numbered as \(1, 2, 3, \ldots\).

However, due to some unfounded rumors, the master started to doubt the butler's loyalty. To test him, the master devised a challenge: he would randomly ask the butler several queries of the following form: "What is the minimum amount recorded between the \(a\)-th and \(b\)-th account entry?"

Your task is to help the butler answer all the queries correctly.

inputFormat

The first line of input contains two integers \(n\) and \(q\), where \(n\) is the total number of account records and \(q\) is the number of queries.

The second line contains \(n\) space-separated integers representing the account records in order.

Each of the following \(q\) lines contains two integers \(a\) and \(b\) (1-indexed), representing a query asking for the minimum record between the \(a\)-th and \(b\)-th entries (inclusive).

outputFormat

For each query, output a single line containing the minimum value among the records in the specified range.

sample

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

1
2
1