Перестановка первых n натуральных чисел занесена в массив. Вывести наименьший индекс массива, содержащий число из интервала от a до b (включительно).

Входные данные

Первая строка содержит два числа n и q (n, q ≤ 105), разделенных пробелом. Вторая строка содержит перестановку из n целых чисел (от 1 до n в любом порядке). Каждая из следующих q строк содержит два целых числа a и b (a ≤ b ≤ 105).

Выходные данные

Вывести в точности q строк, каждая из которых содержит ответ.