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).
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.
Print exactly q lines each containing the answer.