Codeforces Round 204 (Div. 1) |
---|
Закончено |
Рассмотрим последовательность, состоящую из n целых чисел: a1, a2, ..., an. Джефф умеет выполнять следующую операцию с последовательностью 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
Название |
---|