题目描述

传说中，东海龙宫有一副绝世法宝——n 张神迹卡牌，每张卡牌上都写着一个数字。哪吒闹海时，想要施法将龙宫这 n 张卡牌毁灭。

若当前剩余的卡牌数量为 k，哪吒就可以施法将所有数字为 k 的卡牌销毁。这样的操作可以一直进行到没有卡牌可以被毁灭为止。

但哪吒发现，只进行这样的操作可能没办法把所有卡牌消灭，于是他借来了师父太乙真人的法宝，使用一次可以将一张卡牌上的数字改变成他想要的任意一个其他数字。

但是东海龙王发现了哪吒的企图，于是东海龙王会进行 m 次修改操作。第 i 次将第 x_i 张卡牌的数字改变为 y_i。每次东海龙王进行一次操作后，哪吒都想知道至少使用多少次法宝才可以将所有卡牌消灭。

输入格式

• 第一行两个整数 n, m
• 第二行 n 个整数，代表 n 张卡牌上的数字
• 接下来 m 行，每行两个整数 x, y，表示将第 x 张卡牌上的数字改为 y

输出格式

输出 m 行，每行输出一个数字，代表第 i 次操作后至少用多少次法宝才能将卡牌消灭。

数据范围

• 对于 40% 的数据：n, m <= 200
• 对于 60% 的数据：n, m <= 2000
• 对于 100% 的数据：n <= 200000, m <= 200000
• 卡牌上的数字始终 <= n

输入样例

输入样例 1

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

输入样例 2

4 4
4 4 4 4
4 1
3 1
1 1
2 1

输入样例 3

10 10
8 7 2 9 10 6 6 5 5 4
8 1
6 3
6 2
7 10
9 7
9 9
2 4
8 1
1 8
7 7

输出样例

输出样例 1

0
1
1

输出样例 2

0
1
2
3

输出样例 3

1
0
1
2
2
3
3
3
3
2