Реалізуйте запити для знаходження кількості різних чисел на відрізку.
запити offline (тобто всі запити відомі завчавчасно)

Формат вхідних даних

В першому рядку ціле число \(N\), кількість елементів масиву (\(1 \le N \le 5*10^5\)).
В другому рядку елементи масиву. (\(1 \le Ai \le 5*10^5\))
В третьому рядку вводиться число \(K\) - кількість запитів (\(1 \le K \le 5*10^5\))
В кожному з наступних \(K\) рядків міститься по два числа - номера лівого і правого елементів відрізка масиву

Формат вихідних даних

Для кожного запиту виведіть через пробіл - відповідь на запит.

Приклад вхідних даних

5
2 2 2 1 5
2
2 3
2 5

Приклад вихідних даних

1 3