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:
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.
32 51 41 10
0 8 19
101 91 62 41 81 32 101 31 61 102 6
9 15 19 27 30 39 42 48 59 65
Let's consider the first example.
Name |
---|