PERMUN - Permutation

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.


Added by:devu
Date:2012-08-14
Time limit:0.105s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Surendra Baswana

hide comments
2013-12-21 01:35:38 Samil Vargas


Last edit: 2014-01-20 04:40:56
2013-09-04 04:43:57 NeW AcP
nice problem .it is not that trivial to be moved in tutorial.
2013-09-04 04:43:57 :D
It's really pointless to delete "move to tutorial" comments. I'm checking new problems regardless and assessing on my own.

===

For now it doesn't seem that trivial for me, but I'm not to good in this type of problems. If you point out similar ones, I move this to tutorial. If there will be some comment deleting you can drop me an e-mail :)

Last edit: 2012-08-14 20:49:03
2013-09-04 04:43:57 MR. BEAN
1st user of this problem :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.