Задана последовательность a1, a2, ..., an и m запросов lj, rj (1 ≤ lj ≤ rj ≤ n). Для каждого из запросов надо вывести наименьшее из расстояний между такой парой элементов ax и ay (x ≠ y), что:
В тексте выше под расстоянием подразумевается |x - y|.
В первой строке входных данных записана пара целых чисел n, m (1 ≤ n, m ≤ 5·105) — длина последовательности и количество запросов соответственно.
Во второй строке записана последовательность целых чисел a1, a2, ..., an ( - 109 ≤ ai ≤ 109).
Следующие m строк содержат запросы по одному в строке. Каждый из запросов задается парой чисел lj, rj (1 ≤ lj ≤ rj ≤ n) — индексами границ отрезка запроса.
Выведите m чисел — ответы на каждый из запросов. Если для запроса не существует подходящей пары, то следует вывести -1 в качестве ответа на этот запрос.
5 3 1 1 2 3 2 1 5 2 4 3 5
1 -1 2
6 5 1 2 1 3 2 3 4 6 1 3 2 5 2 4 1 6
2 2 3 -1 2
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач