Dany jest ciąg $A_1, A_2, \ldots, A_N$ długości $N$. Napisz program, który wykonuje następujące zapytanie:

• i j: Wypisz liczbę różnych liczb całkowitych w $A_i, A_{i+1}, \ldots, A_j$.

Wejście

Pierwszy wiersz zawiera długość $N$ ciągu ($1 \le N \le 100{,}000$).

Drugi wiersz zawiera $A_1, A_2, \ldots, A_N$ ($1 \le A_i \le 1{,}000{,}000$).

Trzeci wiersz zawiera liczbę $M$ zapytań ($1 \le M \le 100{,}000$).

Czwarty wiersz aż do $M$-tego wiersza zawiera każde zapytanie $i, j$ ($1 \le i \le j \le N$).

Wyjście

Dla każdego zapytania wypisz odpowiedź w osobnym wierszu.

Przykład

Wejście 1

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

Wyjście 1

3
2
3