CF1098D.Eels

Vasya is a big fish lover, and his parents gave him an aquarium for the New Year. Vasya does not have a degree in ichthyology, so he thinks that filling a new aquarium with eels is a good idea. Unfortunately, eels are predators, so Vasya decided to find out how dangerous this idea was.

Getting into one aquarium, eels fight each other until exactly one fish remains. When two eels fight, the big one eats the smaller one (if their weights are equal, then one of them will still eat the other). Namely, let $n$ eels be initially in an aquarium, and the $i$-th of them have a weight of $x_i$. Then $n-1$ battles will occur between them, as a result of which, only one eel will survive. In a battle of two eels with weights $a$ and $b$, where $a \le b$, eel of weight $a$ will be eaten and disappear from the aquarium, and eel of weight $b$ will increase its weight to $a+b$.

A battle between two eels with weights $a$ and $b$, where $a \le b$, is considered dangerous if $b \le 2 a$. For a given set of eels, danger is defined as the maximum number of dangerous battles that can occur among these eels if they are placed in one aquarium.

Now Vasya is planning, which eels he wants to put into an aquarium. He has some set of eels (initially empty). He makes a series of operations with this set. With each operation, he either adds one eel in the set, or removes one eel from the set. Vasya asks you to calculate the danger of the current set of eels after each operation.

瓦西娅非常喜爱鱼类，他的父母在新年时送了他一个水族箱。瓦西娅并没有鱼类学学位，因此他认为往新水族箱里放入鳗鱼是个不错的主意。不幸的是，鳗鱼是肉食性动物，因此瓦西娅决定弄清楚这个想法究竟有多危险。

当若干条鳗鱼被放入同一个水族箱后，它们会彼此争斗，直至仅剩一条鳗鱼存活。当两条鳗鱼发生争斗时，体型较大的那条会吃掉体型较小的那条（若二者体重相等，则其中任意一条仍会吃掉另一条）。具体而言，设初始时水族箱中有 $n$ 条鳗鱼，第 $i$ 条鳗鱼的体重为 $x_i$。那么它们之间将发生 $n-1$ 场战斗，最终仅剩一条鳗鱼存活。在两条体重分别为 $a$ 和 $b$ 的鳗鱼之间的战斗中（其中 $a \le b$），体重为 $a$ 的鳗鱼将被吃掉并从水族箱中消失，而体重为 $b$ 的鳗鱼则将其体重增加至 $a+b$。

对于两条体重分别为 $a$ 和 $b$ 的鳗鱼（其中 $a \le b$）之间的战斗，若满足 $b \le 2 a$，则称该战斗为危险战斗。对于给定的一组鳗鱼，其危险度定义为：当这些鳗鱼全部放入同一个水族箱时，所能发生的危险战斗的最大可能数量。

现在瓦西娅正在规划要放入水族箱中的鳗鱼。他拥有一组鳗鱼（初始为空集），并对此集合执行一系列操作：每次操作要么向集合中添加一条鳗鱼，要么从集合中移除一条鳗鱼。瓦西娅请你帮他计算：在每次操作之后，当前鳗鱼集合的危险度是多少？

The first line of input contains a single integer $q$ ($1 \le q \le 500\,000$), the number of operations that Vasya makes. The next $q$ lines describe operations. Each operation has one of two types :

• + x describes the addition of one eel of weight $x$ to the set ($1 \le x \le 10^9$). Note that in the set there can be several eels of the same weight.
• - x describes the removal of one eel of weight $x$ from a set, and it is guaranteed that there is a eel of such weight in the set.

输入的第一行包含一个整数 $q$（$1 \le q \le 500\,000$），表示 Vasya 执行的操作次数。接下来的 $q$ 行描述这些操作。每种操作为以下两种类型之一：

• + x 表示向集合中添加一条重量为 $x$ 的鳗鱼（$1 \le x \le 10^9$）。注意：集合中可以存在多条重量相同的鳗鱼。
• - x 表示从集合中移除一条重量为 $x$ 的鳗鱼，且保证集合中一定存在一条重量为 $x$ 的鳗鱼。

For each operation, output single integer, the danger of the set of eels after this operation.

对于每次操作，输出一个整数，表示该操作后鳗鱼集合的危险值。

In the third example, after performing all the operations, the set of eels looks like ${1, 1, 4}$. For this set of eels, there are several possible scenarios, if all of them are placed in one aquarium:

• The eel of weight 4 eats the eel of weight 1, and then the second eel of weight 1. In this case, none of the battles are dangerous.
• The eel of weight 1 eats the eel of weight 1, and this battle is dangerous. Now there are two eels in the aquarium, their weights are 4 and 2. The big one eats the small one, and this battle is also dangerous. In this case, the total number of dangerous battles will be 2.

Thus, the danger of this set of eels is 2.

在第三个例子中，执行完所有操作后，鳗鱼集合变为 $\{1, 1, 4\}$。对于该鳗鱼集合，若将全部鳗鱼放入同一个水族箱，则存在若干种可能的情形：

• 重量为 $4$ 的鳗鱼先吃掉一条重量为 $1$ 的鳗鱼，再吃掉另一条重量为 $1$ 的鳗鱼。此时，所有战斗均不危险。
• 一条重量为 $1$ 的鳗鱼吃掉另一条重量为 $1$ 的鳗鱼，该次战斗是危险的。此时水族箱中剩下两条鳗鱼，重量分别为 $4$ 和 $2$；随后较重的鳗鱼吃掉较轻的鳗鱼，该次战斗也是危险的。此时，危险战斗的总数为 $2$。

因此，该鳗鱼集合的危险度为 $2$。