D. Ближайшие равные
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана последовательность a1, a2, ..., an и m запросов lj, rj (1 ≤ lj ≤ rj ≤ n). Для каждого из запросов надо вывести наименьшее из расстояний между такой парой элементов ax и ay (x ≠ y), что:

  • оба индекса элементов попадают в отрезок [lj, rj], то есть lj ≤ x, y ≤ rj;
  • значения элементов равны, то есть ax = ay.

В тексте выше под расстоянием подразумевается |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