You will be given a permutation of first N natural numbers. Then you will be asked to print the smallest index of the array which contains the number between a given range (inclusive). Refer to the example for more details.

Input

First line contains two integers N and Q separated by a space.

Second line contains N integers separated by a space. (From 1 to N in any order)

Now Q line follows: each line contains two integers A and B separated by space.

Output

You must output exactly Q lines each containing  the answer.

Constraints

N ≤ 100000, Q ≤ 100000, A ≤ B ≤ 100000.

Example

Input:
2 2
2 1
1 2
1 1

Output:
1
2

Click here to see my set of problems at SPOJ.