时间限制： 2.0 秒

空间限制： 256 MB

题目描述

A 海滩上放置了一串由不同种类的贝壳组成的贝壳项链。贝壳项链按一条直线顺序放置。现在小 Z 从 I 海滩回到了 A 海滩，他很感兴趣这个海滩上的贝壳情况，希望你帮助他实现以下 3 个任务。

1. 统计 $[L, R]$ 区间上贝壳的种类数；
2. 更换某一位置贝壳的类别；
3. 在某一位置之后放置一个新的贝壳。

输入格式

从标准输入读入数据。

输入包含若干行，第一行包含两个整数 $N, M$，其中 $N$ 代表贝壳的个数，$M$ 代表操作数。

第二行包括 $N$ 个数代表海滩上初始放置的贝壳种类的编号序列 $a_i$，数值范围为 $0$ 至 $2N$ 的整数。

第三行至第 $M+2$ 行代表具体操作，操作为以下三类：

• $1~L~R$：查询 $[L, R]$ 区间上贝壳的种类数，$L$ 和 $R$ 为 1-based 下标。
• $2~P~V$：更换第 $P$ 个位置的贝壳为 $V$，保证 $V$ 为 $0$ 至 $2N$ 的整数，下标为 1-based 下标。
• $3~P~V$：在第 $P$ 个位置后插入一个编号为 $V$ 的贝壳，保证 $V$ 为 $0$ 至 $2N$ 的整数，下标为 1-based 下标。

输出格式

输出到标准输出。

对于每一个查询，输出查询的结果。

6 5
1 1 2 3 4 1
1 1 6
2 1 5
1 1 3
3 1 1
1 1 3

4
3
2

样例 1 解释

• 对于第一个操作 1 1 6，查询[1,6]贝壳种类数为4。{1,2,3,4}
• 对于第二个操作 2 1 5，将第1个贝壳变更为编号为5的贝壳，此时贝壳为(5,1,2,3,4,1)。
• 对于第三个操作 1 1 3，查询[1,3]贝壳种类数为3。{5,1,2}
• 对于第四个操作 3 1 1，在第一个贝壳后插入编号为1的贝壳，此时贝壳为(5,1,1,2,3,4,1)。
• 对于第五个操作 1 1 3，查询[1,3]贝壳种类数为2。{5,1,1}

样例 2

见题目文件区的 2.in 和 2.ans。

子任务

本题保证所有的数据随机生成，输入数据的规模符合下表。样例 2 采用与测试点 21-25 相同的生成器生成。贝壳的种类编号 $a_i ≤ 2\times 10^5$，每次查询 $0 ≤ L ≤ R ≤ N$。