不点两面(hard version)
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

x魂是一款深受acmer喜爱的立直麻将游戏,在x魂中,认为不点两面听牌的牌是比较安全的,本题需要你求出在只有万子的x魂中,有几种牌是比较安全的。

具体来说,每张牌上有一个数字,数字范围在1m之间。场上还有一个对手的牌河,对手的牌河中有若干张对手已经打出的牌。定义比较安全牌为:该牌上写有的数字x满足x-3至少在对手牌河里出现过一次。

请你求出,在m种牌中有几种牌是比较安全的。

对手的牌河初始为空,对手会不断向牌河中加入或移出一张牌共q次,你需要在每次对手操作后都给出当前状况下的答案。

输入描述:

输入第一行是两个整数,含义如题目所述。

接下来q行,每行输入两个整数,表示一次操作,具体来说:

表示对手向牌河中加入了一张num

表示对手从牌河中移出了一张num,保证移出的牌操作前一定在牌河里有至少一张。

注意牌河中可能有写有相同数字的牌出现多次。

输出描述:

输出q行,第i行表示第i次操作后,m种牌中有几种牌是比较安全的。
示例1

输入

复制
10 5
1 4
1 10
1 4
2 4
2 4

输出

复制
2
2
2
2
1