合并

题目限制

3000 ms 512 M

题目描述

给定一组数的集合 $a[1] \sim a[n]$，维护 $m$ 次操作：

1 i x：将 $a[i]$ 修改为 $x$；

2：指定一种“替换”步骤：选择两个相同数字 $a[i],a[j]$，从集合中删去这两个数并把 $a[i]+1$ 加入集合。查询当可以进行任意次替换步骤之后，集合中至多可能存在多少种不同数字。

输入格式

第一行输入两个正整数n,m； 第二行输入n个正整数a[i]； 之后m行，每行描述一个操作。 其中n,m≤5e5。

输出格式

对于每个操作2，输出一行一个数表示答案。

数据范围

对于100%的数据，$1\le n,m,x,a[i]\le 5\times 10^5$。

子任务1（#1~#4）：$m=1$；

子任务2（#5~#8）：$n,m\le 2000$；

子任务3（#9~#12）：$i\le 10$；

子任务4（#13~#16）：$a[i],i,x$ 均随机生成；

子任务5（#17~#22）：无额外限制。

输入样例

5 9
1 2 3 4 5
2
1 1 2
2
1 3 2
2
1 4 3
2
1 5 3
2

输出样例

5
4
4
3
3