Problem description

Dany jest ciąg liczb naturalnych A_i oraz dużo zapytań postaci: dla podanej pary (x,y) jak daleko od siebie oddalone są najbliższe wystąpienia liczb x oraz y w tablicy. Dokładniej, niech S_x = {i : A_i = x} oraz S_y = {i : A_i = y}, wtedy celem zapytania jest odpowiedzieć na pytanie o min {|i−j| : i ∈ S_x ∧ j ∈ S_y}. Czy potrafisz szybko odpowiedzieć na tego typu zapytania?

Napisz program, który: wczyta ciąg i zapytania, wyznaczy odpowiedzi dla wszystkich zapytań i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca liczbę elementów ciągu. W drugim wierszu wejścia znajduje się N liczb naturalnych A_i pooddzielanych pojedynczymi odstępami. Są to kolejne elementy ciągu, o którym mowa powyżej.

W trzecim wierszu wejścia znajduje się jedna liczba naturalna Q, określająca liczbę zapytań. W kolejnych Q wierszach znajduje się opis kolejnych zapytań, po jednym w wierszu. Opis każdego zapytania składa się z dwóch liczb naturalnych x_i oraz y_i oznaczających zapytanie (x_i,y_i) o odległość najbliższych wystąpień liczb x_i oraz y_i w ciągu A.

Wyjście

Twój program powinien wypisać na wyjście dokładnie Q wierszy. W i-tym wierszu powinna się znaleźć odpowiedź dla i-tego zapytania: odległość pomiędzy dwoma najbliższymi wystąpieniami liczb x_i oraz y_i w ciągu A. Jeśli taka para w ogóle nie występuje w ciągu, zamiast tego należy wypisać tylko jedno słowo NIE.

Ograniczenia

1 ≤ N ≤ 100 000, 1 ≤ Q ≤ 1 000 000, 1 ≤ A_i ≤ 10⁹, 1 ≤ x_i, y_i ≤ 10⁹.

Przykład

7
2 1 5 2 4 1 4
4
2 5
1 2
7 1
5 4

1
1
NIE
2