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

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.