Problem hidden

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 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.


Adicionado por:devu
Data:2012-08-14
Tempo limite:0.105s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Surendra Baswana
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.