Перестановка

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

Вхідні дані

Перший рядок містить два числа n та q (n, q ≤ 10^5), розділених пропуском. Другий рядок містить перестановку з n цілих чисел (від 1 до n у довільному порядку). Кожний з наступних q рядків містить два цілі числа a та b (a ≤ b ≤ 10^5).

Вихідні дані

Вивести в точності q рядків, кожний з яких містить відповідь.

Приклади