CF1774F2.Magician and Pigs (Hard Version)

This is the hard version of the problem. The only difference between the two versions is the constraint on $n$ and $x$. You can make hacks only if both versions of the problem are solved.

Little09 has been interested in magic for a long time, and it's so lucky that he meets a magician! The magician will perform $n$ operations, each of them is one of the following three:

• $1\ x$: Create a pig with $x$ Health Points.
• $2\ x$: Reduce the Health Point of all living pigs by $x$.
• $3$: Repeat all previous operations. Formally, assuming that this is the $i$-th operation in the operation sequence, perform the first $i-1$ operations (including "Repeat" operations involved) in turn.

A pig will die when its Health Point is less than or equal to $0$.

Little09 wants to know how many living pigs there are after all the operations. Please, print the answer modulo $998\,244\,353$.

这是该问题的困难版本。两个版本之间的唯一区别在于对 $n$ 和 $x$ 的约束条件。仅当两个版本的问题均被解决时，才允许进行 Hack。

Little09 长期以来对魔法很感兴趣，而他非常幸运地遇到了一位魔术师！这位魔术师将执行 $n$ 次操作，每次操作为以下三种之一：

• $1\ x$：创建一只具有 $x$ 点生命值（Health Points）的猪；
• $2\ x$：将所有现存猪的生命值减少 $x$；
• $3$：重复之前所有的操作。形式化地说，假设这是操作序列中的第 $i$ 次操作，则依次执行前 $i-1$ 次操作（包括其中涉及的所有“重复”操作）。

当一只猪的生命值小于等于 $0$ 时，它就会死亡。

Little09 想知道在所有操作执行完毕后，还剩多少只存活的猪。请输出答案对 $998\,244\,353$ 取模的结果。

The first line contains a single integer $n$ ($1\leq n\leq 8\cdot 10^5$) — the number of operations.

Each of the following $n$ lines contains an operation given in the form described in the problem statement. It's guaranteed that $1\leq x\leq 10^9$ in operations of the first two types.

第一行包含一个整数 $n$（$1\leq n\leq 8\cdot 10^5$）—— 操作的数量。

接下来的 $n$ 行中，每行包含一个按题目描述形式给出的操作。保证在前两种类型的操作中，$1\leq x\leq 10^9$。

Print a single integer — the number of living pigs after all the operations, modulo $998\,244\,353$.

输出一个整数——所有操作结束后存活的猪的数量，对 $998\,244\,353$ 取模。

In the first example, the operations are equivalent to repeating four times: create a pig with $8$ Health Points and then reduce the Health Points of all living pigs by $3$. It is easy to find that there are two living pigs in the end with $2$ and $5$ Health Points.

在第一个例子中，这些操作等价于重复执行四次：创建一只生命值为 $8$ 的猪，然后将所有存活猪的生命值减少 $3$。很容易发现，最终有两只猪存活，其生命值分别为 $2$ 和 $5$。