Problem description

Dany jest ciąg N liczb naturalnych oraz Q zapytań o spójne przedziały tego ciągu.

Napisz program, który: wczyta ciąg liczb, wyznaczy liczbę różnych liczb na przedziałach i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca długość ciągu. W drugim wierwszu wejścia znajduje się ciąg N liczb naturalnych A_i, pooddzielanych pojedynczymi odstępami – ciąg, o którym mowa powyżej. W trzecim wierszu wejścia znajduje się liczba naturalna Q, określająca liczbę zapytań. W kolejnych Q wierszach znajduje się ciąg kolejnych zapytań. Każde zapytanie (w osobnym wierszu) składa się z dwóch liczb naturalnych s_i oraz f_i, pooddzielanych pojedynczymi odstępami – indeks początku i końca przedziału, o który pyta i-te zapytanie.

Pozycje w ciągu numerujemy kolejnymi liczbami naturalnymi od 1 do N włącznie.

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 – liczba różnych liczb na przedziale.

Ograniczenia

1 ≤ N ≤ 100 000, 1 ≤ Q ≤ 100 000, 0 ≤ A_i ≤ 10⁹.

Przykład

6
1 2 2 3 2 1
4
2 5
1 4
4 6
2 3

2
3
3
1