Problems
Permutation
Permutation
You are given a permutation of first n positive integers in array. Print the smallest index of array that contains the number in the range from a to b (inclusive).
Input data
First line contains two integers n and q (n, q ≤ 10^5
) separated by a space. Second line contains a permutation of n integers (from 1 to n in any order). Then q lines follow: each line contains two integers a and b (a ≤ b ≤ 10^5
) separated by space.
Output data
Print exactly q lines each containing the answer.
Examples
Input example #1
2 2 2 1 1 2 1 1
Output example #1
1 2