Рассмотрим последовательность, состоящую из 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 и вопросы. Помогите Джеффу, ответьте на его вопросы.
Выходные данные
В q строках выведите ответы на вопросы Джеффа. Ответы на вопросы выводите в том порядке, в котором они следуют во входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 2 1 1 2
5
1 5
1 1
2 2
1 3
2 3
|
2
1
1
2
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
|