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 Iput-Output for more details.

Input

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

Second line contains N integers separeted 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 containg  the answer.

Constraint:

N<=100000,Q<=100000,A<=B<=100000.

Example

Input:

2 2
2 1
1 2
1 1
2 2
2 1

Output:
1
2

Click here to see my set of problems at Spoj.