% Источник: СПБ АУ, пары бакалавров, весенний семестр 2014-2015
% Тестить можно здесь: http://www.spoj.com/problems/DQUERY/

\begin{problem}{Различные числа}
{distinctnum.in}{distinctnum.out}
{1 секунда}{256 мегабайт}{}

Сколько различных чисел на отрезке массива?

\InputFile

На первой строке длина массива $n$ ($1 \le n \le 300\,000$).
На второй строке $n$ целых чисел от $0$ до $10^9{-}1$.
На третьей строке количество запросов $q$ ($1 \le q \le 300\,000$).
Следующие $q$ строк содержат описание запросов, по одному на строке.
Каждый запрос задаётся парой целых чисел $l$, $r$ ($1 \le l \le r \le n$).

\OutputFile

Выведите ответы на запросы по одному в строке.

\Examples

\begin{example}
\exmp{
5
1 1 2 1 3
3
1 5
2 4
3 5
}{
3
2
3
}%
\end{example}

\end{problem}
