CF2025G Variable Damage

Monocarp is gathering an army to fight a dragon in a videogame. The army consists of two parts: the heroes and the defensive artifacts. Each hero has one parameter — his health. Each defensive artifact also has one parameter — its durability. Before the battle begins, Monocarp distributes artifacts to the heroes so that each hero receives at most one artifact. The battle consists of rounds that proceed as follows: - first, the dragon deals damage equal to $ \frac{1}{a + b} $ (a real number without rounding) to each hero, where $ a $ is the number of heroes alive and $ b $ is the number of active artifacts; - after that, all heroes with health $ 0 $ or less die; - finally, some artifacts are deactivated. An artifact with durability $ x $ is deactivated when one of the following occurs: the hero holding the artifact either dies or receives $ x $ total damage (from the start of the battle). If an artifact is not held by any hero, it is inactive from the beginning of the battle. The battle ends when there are no heroes left alive. Initially, the army is empty. There are $ q $ queries: add a hero with health $ x $ or an artifact with durability $ y $ to the army. After each query, determine the maximum number of rounds that Monocarp can survive if he distributes the artifacts optimally.

The first line contains one integer $ q $ ( $ 1 \le q \le 3 \cdot 10^5 $ ) — the number of queries. In the $ i $ -th of the following $ q $ lines, there are two integers $ t_i $ and $ v_i $ ( $ t_i \in \{1, 2\} $ ; $ 1 \le v_i \le 10^9 $ ) — the type of the query and the value of the query parameter. If the type is $ 1 $ , a hero with health $ v_i $ is added. If the type is $ 2 $ , an artifact with durability $ v_i $ is added.

Print $ q $ integers. After each query, output the maximum number of rounds that Monocarp can survive if he distributes the artifacts optimally.

Let's consider the first example. - An artifact with durability $ 5 $ is added. Since there are no heroes yet, the battle ends immediately. - A hero with health $ 4 $ is added. Monocarp can give him an artifact with durability $ 5 $ . First, there are rounds in which the hero takes $ \frac{1}{1 + 1} = \frac{1}{2} $ damage. After $ 8 $ such rounds, a total of $ 4 $ damage will have been dealt, and the hero will die, while the artifact will deactivate. There are no more heroes alive, so the battle ends after $ 8 $ rounds. - A hero with health $ 10 $ is added. Now let the artifact with durability $ 5 $ be with this hero. Then, in the first $ 12 $ rounds, the heroes will take $ 12 \cdot \frac{1}{2 + 1} = 4 $ damage, and the first hero will die. The second hero has $ 6 $ health left, and the artifact has $ 1 $ durability. Now the damage is $ \frac{1}{2} $ , so after another $ 2 $ rounds, the artifact will deactivate. The second hero has $ 5 $ health left. After another $ 5 $ rounds, the second hero will die. Therefore, the answer is $ 12 + 2 + 5 = 19 $ .