Migrated from Lutece 2950 Colorful Scarf

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

本题解法:启发式合并/线段树合并 注意:u和v可能相同 blackbird买了一条新围巾，它是由 $n$ 块不同颜色的布料顺次拼接而成的，第 $i$ 块布料的颜色是 $c_i$。 blackbird对围巾的颜色不太满意，于是找来颜料和刷子。由于它很笨，每次操作只能将某一种颜色的布料全部涂成另一种颜色。同时，它还想知道当前围巾上有多少颜色段（详见样例解释）。

Input

第一行两个整数 $n, m$ ,分别表示布料的块数和操作次数。 第二行 $n$ 个整数 $c_1,c_2,...,c_n$， 分别表示每一块的颜色。 接下来 $m$ 行，首先输入一个整数 $op$

• 如果 $op = 1$, 接着输入两个整数 $u, v$ ，表示将所有颜色为 $u$ 的块涂成颜色 $v$。
• 如果 $op = 2$, 表示询问当前围巾上有多少个颜色段。

Output

对于每个询问，输出一行一个整数，表示当前围巾上有多少个颜色段。

Samples

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

5
4
1

Constraints

$1 \le n, m, c_i, u, v \le 10^6$

Note

第一次涂色前，围巾上有 $[1,1], [4], [5], [1], [4]$ 五个颜色段。 第一次涂色后，围巾上有 $[1,1], [4,4], [1], [4]$ 四个颜色段。 第二次涂色后，围巾上有 $[1,1,1,1,1,1]$ 一个颜色段。

Resources

2023 UESTC ICPC Training for Data Structures