D. Джефф и удаление периодов
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим последовательность, состоящую из n целых чисел: a1, a2, ..., an. Джефф умеет выполнять следующую операцию с последовательностью a:

  • выбрать три целых числа v, t, k (1 ≤ v, t ≤ n; 0 ≤ k; v + tk ≤ n), такие что av = av + t, av + t = av + 2t, ..., av + t(k - 1) = av + tk;
  • удалить элементы av, av + t, ..., av + tk из последовательности, при этом оставшиеся элементы последовательности нумеруются заново a1, a2, ..., an - k - 1;
  • перемешать элементы новой последовательности a.

Красота последовательности a — это минимальное количество операций, с помощью которых можно удалить все ее элементы.

Джефф записал последовательность из m целых чисел b1, b2, ..., bm. Теперь Джеффа интересуют q вопросов. Каждый из вопросов задается двумя целыми числами li, ri (1 ≤ li ≤ ri ≤ m). Ответ на i-ый вопрос: значение красоты последовательности bli, bli + 1, ..., bri. Вам задана последовательность b и вопросы. Помогите Джеффу, ответьте на его вопросы.

Входные данные

Первая строка содержит целое число m (1 ≤ m ≤ 105). Следующая строка содержит m целых чисел b1, b2, ..., bm (1 ≤ bi ≤ 105).

Во третьей строке записано целое число q (1 ≤ q ≤ 105) — количество вопросов. Следующие q строк содержат пары чисел, i-ая из них содержит пару целых чисел li, ri (1 ≤ li ≤ ri ≤ m) — описание i-го вопроса.

Выходные данные

В q строках выведите ответы на вопросы Джеффа. Ответы на вопросы выводите в том порядке, в котором они следуют во входных данных.

Примеры
Входные данные
5
2 2 1 1 2
5
1 5
1 1
2 2
1 3
2 3
Выходные данные
2
1
1
2
2
Входные данные
10
2 1 3 3 3 3 1 3 1 1
10
4 8
2 10
1 10
4 4
1 3
2 4
6 7
1 9
2 5
1 1
Выходные данные
2
3
3
1
3
2
2
3
2
1