Дан массив \(a\), состоящий из \(n\) целых чисел. Вам нужно обработать \(q\) запросов двух типов:
- \(1~p~x\) — присвоить элементу массива на позиции \(p\) значение \(x\);
- \(2~l~r\) — подсчитать количество пар позиций \((i, j)\), где \(l \le i < j \le r\) и \(a_i \ne a_j\).
Обратите внимание, что запросы в этой задаче закодированы; каждый следующий запрос вы сможете раскодировать, вычислив ответ на предшествующий ему запрос второго типа.
Выходные данные
На каждый запрос второго типа выведите ответ — количество пар позиций \((i, j)\), где \(l \le i < j \le r\) и \(a_i \ne a_j\).
Примечание
В первом примере реальные запросы (после декодирования) такие:
- 2 1 3
- 1 1 3
- 2 1 3
- 1 2 3
- 2 1 3
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 3
5
2 0 2
1 0 2
2 0 2
1 2 0
2 1 0
|
3 2 0
|
|
2
|
7
1 3 4 4 7 1 3
3
2 1 6
2 1 0
2 5 6
|
13 18 0
|