Description

There are $n$ puddings in a line, and we will perform $m$ operations. An operation may recolor all puddings of one color into another color, or ask how many color segments there are at the moment.

For example, four puddings with colors $1, 2, 2, 1$ have $3$ color segments.

Input Format

The first line contains two integers, the number of puddings $n$ and the number of operations $m$.
The second line contains $n$ integers; the $i$-th integer is the color $a_i$ of the $i$-th pudding.
Then there are $m$ lines, each describing one operation. Each line starts with an integer $op$ indicating the type:

• If $op = 1$, then two integers $x, y$ follow, meaning recolor all puddings of color $x$ to color $y$.
• If $op = 2$, it denotes a query.

Output Format

For each query, output one integer on a single line, indicating the answer.

4 3
1 2 2 1
2
1 2 1
2

3
1

Hint

Sample 1 Explanation
Initially the colors are $1, 2, 2, 1$, and the three color segments are $[1, 1], [2, 3], [4, 4]$.
After one operation, the colors become $1, 1, 1, 1$, leaving only one segment $[1, 4]$.

Constraints
For all test points, it is guaranteed that $1 \leq n, m \leq 10^5$, $1 \leq a_i, x, y \leq 10^6$.

Notes
Please note that it is not guaranteed that color IDs are at most $n$, it is also not guaranteed that $x \neq y$, and $m$ is not an upper bound on color IDs.

Translated by ChatGPT 5