A15609. 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$ .

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.

Print a single integer — the number of living pigs after all the operations, modulo $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.