我不会感到孤独,也不会悲伤……在一切都被埋葬之前。
留下一串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(含)的子段的内存。
输出
对于每个查询,打印一行并包含一个整数——调用的子段的内存。
示例
输入 #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
输出 #1
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
输出 #2
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。