Не буду ни грустить, ни страдать от одиночества... пока всё не закончится.
Нитка из n бусинок оставлена, как сообщение об уходе. Бусинки пронумерованы от 1 до n слева направо, каждая имеет форму, выраженную целым числом от 1 до n, включительно. Некоторые бусинки могут иметь одинаковую форму.
Память формы x в некотором отрезке бусинок определена как разность между последней и первой позициями, где форма x встречается на этом отрезке. Память подотрезка бусинок равняется сумме памяти по всем формам, встречающимся на этом отрезке.
Иногда формы бусинок меняются, и с ними меняются значения памяти. Иногда вам нужно находить память для некоторых подотрезков.
Выходные данные
Для каждого запроса выведите отдельную строку с величиной памяти данного отрезка.
Примечание
В начале формы бусинок имеют вид (1, 2, 3, 1, 3, 2, 1).
Рассмотрим запросы и изменения формы по очереди:
- 2 3 7: память на отрезке [3, 7] равна (7 - 4) + (6 - 6) + (5 - 3) = 5;
- 2 1 3: память на отрезке [1, 3] равна (1 - 1) + (2 - 2) + (3 - 3) = 0;
- 1 7 2: форма бусинки 7 меняется на 2. В результате формы бусинок будут выглядеть следующим образом: (1, 2, 3, 1, 3, 2, 2);
- 1 3 2: форма бусинки 3 меняется на 2. В результате формы бусинок будут выглядеть следующим образом: (1, 2, 2, 1, 3, 2, 2);
- 2 1 6: память на отрезке [1, 6] равна (4 - 1) + (6 - 2) + (5 - 5) = 7;
- 2 5 7: память на отрезке [5, 7] равна (7 - 6) + (5 - 5) = 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 6
1 2 3 1 3 2 1
2 3 7
2 1 3
1 7 2
1 3 2
2 1 6
2 5 7
|
5
0
7
1
|
|
2
|
7 5
1 3 2 1 4 2 3
1 1 4
2 2 3
1 1 7
2 4 5
1 1 7
|
0
0
|