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

First line contains two integers n and q (n, q ≤ 105) 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 ≤ 105) separated by space.

Output

Print exactly q lines each containing the answer.