L. Различные на отрезке

Дан массив. На каждый запрос $(l, r)$ нужно сказать, сколько различных значений встречается среди $a_l, \ldots, a_r$.

Обновлений нет, все запросы известны заранее - значит, можно отвечать на них не в том порядке, в котором они заданы. Это и есть алгоритм Мо.

В первой строке - число $n$ ($1 \le n \le 10^5$).

Во второй строке - $n$ чисел $a_i$ ($1 \le a_i \le 10^6$).

В третьей строке - число запросов $q$ ($1 \le q \le 10^5$).

В следующих $q$ строках - пары $l$ и $r$ ($1 \le l \le r \le n$).

Для каждого запроса выведите количество различных значений на отрезке.