这是问题的困难版本。两个版本之间的唯一区别是对 $$$n$$$ 和 $$$x$$$ 的约束。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
小09对魔术很感兴趣,很幸运能遇到魔术师!魔术师将执行$$$n$$$操作,每个操作都是以下三种之一:
- $$$1\ x$$$:创建一头拥有 $$$x$$$ 生命值的猪。
- $$$2\ x$$$:将所有活猪的生命值降低$$$x$$$。
- $$$3$$$:重复之前的所有操作。形式上,假设这是操作序列中的第$$$i$$$操作,依次执行前$$$i-1$$$操作(包括涉及的“重复”操作)。
当猪的生命值小于或等于$$$0$$$时,猪就会死亡。
Little09想知道所有操作之后还有多少头活猪。请打印出对 $$$998\,244\,353$$$ 取模的答案。
输入
第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 8\cdot 10^5$$$) — 操作数。
以下 $$$n$$$ 行中的每一行都包含以问题陈述中描述的形式给出的操作。在前两种类型的运算中,保证$$$1\leq x\leq 10^9$$$。
输出
打印一个整数——所有操作后的活猪数量,模 $$$998\,244\,353$$$。
示例
输入 #1
4 1 8 2 3 3 3
输出 #1
2
输入 #2
6 1 5 1 6 2 2 3 1 4 3
输出 #2
5
输入 #3
12 2 1 1 15 1 9 3 1 12 2 2 1 13 3 2 1 1 9 1 8 3
输出 #3
17
注意
在第一个示例中,操作相当于重复四次:创建一头拥有 $$$8$$$ 生命值的猪,然后将所有活着的猪的生命值减少 $$$3$$$。很容易发现最后有两只活猪,生命值$$$2$$$和$$$5$$$。