Permutation

Input

The first line contains two integers $n$ and q~(1 \le n, q \le 10^5) — the size of the permutation and the number of queries, respectively.

The second line contains a permutation of $n$ distinct integers from $1$ to $n$.

Each of the next $q$ lines contains two integers $u$ and v~(1 \le u \le v \le 10^5), defining the boundaries of the segment.

Output

For each query, print the smallest index of the array that contains a number from the segment $[u,v]$. Print the answers one per line.

Examples