C. Goodbye Souvenir
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Не буду ни грустить, ни страдать от одиночества... пока всё не закончится.

Нитка из n бусинок оставлена, как сообщение об уходе. Бусинки пронумерованы от 1 до n слева направо, каждая имеет форму, выраженную целым числом от 1 до n, включительно. Некоторые бусинки могут иметь одинаковую форму.

Память формы x в некотором отрезке бусинок определена как разность между последней и первой позициями, где форма x встречается на этом отрезке. Память подотрезка бусинок равняется сумме памяти по всем формам, встречающимся на этом отрезке.

Иногда формы бусинок меняются, и с ними меняются значения памяти. Иногда вам нужно находить память для некоторых подотрезков.

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

В первой строке заданы два целых числа n и m (1 ≤ n, m ≤ 100 000) — число бусинок и суммарное число изменений формы и запросов памяти.

Во второй строке задано n целых чисел a1, a2, ..., an (1 ≤ ai ≤ n) — начальные формы бусинок 1, 2, ..., n, соответственно.

Далее, в m строках заданы запросы памяти и изменения формы бусинок, по одному в строке. Строка имеет вид:

  • 1 p x (1 ≤ p ≤ n, 1 ≤ x ≤ n), что означает, что форма бусинки p меняется на x, или
  • 2 l r (1 ≤ l ≤ r ≤ n), что означает запрос величины памяти на отрезке с бусинки l по бусинку r, включительно.
Выходные данные

Для каждого запроса выведите отдельную строку с величиной памяти данного отрезка.

Примеры
Входные данные
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
Входные данные
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
Примечание

В начале формы бусинок имеют вид (1, 2, 3, 1, 3, 2, 1).

Рассмотрим запросы и изменения формы по очереди:

  1. 2 3 7: память на отрезке [3, 7] равна (7 - 4) + (6 - 6) + (5 - 3) = 5;
  2. 2 1 3: память на отрезке [1, 3] равна (1 - 1) + (2 - 2) + (3 - 3) = 0;
  3. 1 7 2: форма бусинки 7 меняется на 2. В результате формы бусинок будут выглядеть следующим образом: (1, 2, 3, 1, 3, 2, 2);
  4. 1 3 2: форма бусинки 3 меняется на 2. В результате формы бусинок будут выглядеть следующим образом: (1, 2, 2, 1, 3, 2, 2);
  5. 2 1 6: память на отрезке [1, 6] равна (4 - 1) + (6 - 2) + (5 - 5) = 7;
  6. 2 5 7: память на отрезке [5, 7] равна (7 - 6) + (5 - 5) = 1.