Сколько различных на отрезке

Дан массив. Для каждого запроса $[l, r]$ выведите количество различных значений на этом отрезке. Массив не меняется, все запросы известны заранее.

Первая задача, где дерево работает не онлайн, а вместе с сортировкой запросов.

В первой строке $n$ ($1 \le n \le 10^5$). Во второй — $n$ чисел $a_i$ ($1 \le a_i \le 10^9$). В третьей — $m$ ($1 \le m \le 10^5$). Далее $m$ строк по два числа $l$ и $r$ ($1 \le l \le r \le n$).

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