Задана последовательность a1, a2, ..., an и m запросов lj, rj (1 ≤ lj ≤ rj ≤ n). Для каждого из запросов надо вывести наименьшее из расстояний между такой парой элементов ax и ay (x ≠ y), что:
- оба индекса элементов попадают в отрезок [lj, rj], то есть lj ≤ x, y ≤ rj;
- значения элементов равны, то есть ax = ay.
В тексте выше под расстоянием подразумевается |x - y|.
Выходные данные
Выведите m чисел — ответы на каждый из запросов. Если для запроса не существует подходящей пары, то следует вывести -1 в качестве ответа на этот запрос.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
1 1 2 3 2
1 5
2 4
3 5
|
1
-1
2
|
|
2
|
6 5
1 2 1 3 2 3
4 6
1 3
2 5
2 4
1 6
|
2
2
3
-1
2
|