You are given a permutation of first \textbf{n} positive integers in array. Print the smallest index of array that contains the number in the range from \textbf{a} to \textbf{b} (inclusive). \InputFile First line contains two integers \textbf{n} and \textbf{q} (\textbf{n}, \textbf{q} ≤ \textbf{10^5}) separated by a space. Second line contains a permutation of \textbf{n }integers (from \textbf{1} to \textbf{n} in any order). Then \textbf{q} lines follow: each line contains two integers \textbf{a }and \textbf{b} (\textbf{a }≤ \textbf{b} ≤ \textbf{10^5}) separated by space. \OutputFile Print exactly \textbf{q} lines each containing the answer.