CF848C.Goodbye Souvenir

I won't feel lonely, nor will I be sorrowful... not before everything is buried.

A string of n beads is left as the message of leaving. The beads are numbered from 1 to n from left to right, each having a shape numbered by integers between 1 and n inclusive. Some beads may have the same shapes.

The memory of a shape x in a certain subsegment of beads, is defined to be the difference between the last position and the first position that shape x appears in the segment. The memory of a subsegment is the sum of memories over all shapes that occur in it.

From time to time, shapes of beads change as well as the memories. Sometimes, the past secreted in subsegments are being recalled, and you are to find the memory for each of them.

我不会感到孤独，也不会悲伤……直到一切被掩埋。

一串由 n 颗珠子组成的字符串，作为离别时留下的信息。珠子从左到右编号为 1 到 n，每颗珠子的形状用 1 到 n（含）之间的整数表示。某些珠子可能具有相同的形状。

在珠子序列的某个子段中，形状 x 的“记忆值”定义为：形状 x 在该子段中最后一次出现的位置与第一次出现的位置之差。一个子段的“记忆值”则定义为：该子段中所有出现过的形状的记忆值之和。

随着时间推移，珠子的形状会发生变化，其记忆值也随之改变。有时，子段中封存的过往秘密会被唤起，此时你需要计算每个指定子段的记忆值。

The first line of input contains two space-separated integers n and m (1 ≤ n, m ≤ 100 000) — the number of beads in the string, and the total number of changes and queries, respectively.

The second line contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ n) — the initial shapes of beads 1, 2, ..., n, respectively.

The following m lines each describes either a change in the beads or a query of subsegment. A line has one of the following formats:

• 1 p x (1 ≤ p ≤ n, 1 ≤ x ≤ n), meaning that the shape of the p-th bead is changed into x;
• 2 l r (1 ≤ l ≤ r ≤ n), denoting a query of memory of the subsegment from l to r, inclusive.

输入的第一行包含两个以空格分隔的整数 $n$ 和 $m$（$1 \leq n, m \leq 100\,000$）——分别表示字符串中珠子的数量，以及总共的修改操作与查询操作次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq n$）——分别表示第 $1, 2, \dots, n$ 颗珠子的初始形状。

接下来的 $m$ 行每行描述一次对珠子的修改操作或对某个子区间的查询操作。每行具有以下两种格式之一：

• 1 p x（$1 \leq p \leq n$, $1 \leq x \leq n$），表示将第 $p$ 颗珠子的形状更改为 $x$；
• 2 l r（$1 \leq l \leq r \leq n$），表示查询区间 $[l, r]$（含端点）的记忆值。

For each query, print one line with an integer — the memory of the recalled subsegment.

对于每个查询，输出一行，包含一个整数——被回忆子段的内存值。

The initial string of beads has shapes (1, 2, 3, 1, 3, 2, 1).

Consider the changes and queries in their order:

1. 2 3 7: the memory of the subsegment [3, 7] is (7 - 4) + (6 - 6) + (5 - 3) = 5;
2. 2 1 3: the memory of the subsegment [1, 3] is (1 - 1) + (2 - 2) + (3 - 3) = 0;
3. 1 7 2: the shape of the 7-th bead changes into 2. Beads now have shapes (1, 2, 3, 1, 3, 2, 2) respectively;
4. 1 3 2: the shape of the 3-rd bead changes into 2. Beads now have shapes (1, 2, 2, 1, 3, 2, 2) respectively;
5. 2 1 6: the memory of the subsegment [1, 6] is (4 - 1) + (6 - 2) + (5 - 5) = 7;
6. 2 5 7: the memory of the subsegment [5, 7] is (7 - 6) + (5 - 5) = 1.

初始珠子串的形状为 $(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$。