Vasya 是个大鱼爱好者,新年父母送了他一个水族箱。 Vasya 没有鱼类学学位,因此他认为在新的水族馆里养鳗鱼是个好主意。不幸的是,鳗鱼是掠食者,所以瓦夏决定找出这个想法有多危险。
进入一个水族馆,鳗鱼互相争斗,直到只剩下一条鱼。当两条鳗鱼打架时,大的鳗鱼会吃掉较小的鳗鱼(如果它们的重量相等,那么其中一只仍然会吃掉另一只)。也就是说,让 $$$n$$$ 鳗鱼最初位于水族箱中,其中第 $$$i$$$ 的重量为 $$$x_i$$$。然后它们之间会发生 $$$n-1$$$ 战斗,结果只有一条鳗鱼能够幸存。在两条重量为 $$$a$$$ 和 $$$b$$$ 的鳗鱼的战斗中,其中 $$$a \le b$$$,重量为 $$$a$$$ 的鳗鱼将被吃掉并从水族箱中消失,而重量为 $$$b$$$ 的鳗鱼将增加其重量至 $$$a+b$$$。
两条重量为 $$$a$$$ 和 $$$b$$$ 的鳗鱼之间的战斗,其中 $$$a \le b$$$,如果 $$$b \le 2 a$$$ 则被认为是危险的。对于一组给定的鳗鱼,危险被定义为如果将它们放入一个水族箱中,这些鳗鱼之间可能发生的危险战斗的最大数量。
现在 Vasya 正在计划,他想将这些鳗鱼放入水族馆。他有一些鳗鱼(最初是空的)。他用这个集合做了一系列的操作。在每次操作中,他要么在集合中添加一条鳗鱼,要么从集合中删除一条鳗鱼。 Vasya 要求您在每次操作后计算当前一组鳗鱼的危险度。
输入
输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 500\,000$$$),即 Vasya 进行的操作数。接下来的 $$$q$$$ 行描述了操作。每个操作都有两种类型之一:
- + x 描述将一条重量为 $$$x$$$ 的鳗鱼添加到集合中 ($$$1 \le x \le 10^9$$$)。请注意,该组中可以有几条重量相同的鳗鱼。
- - x描述从一组中取出一条重量为$$$x$$$的鳗鱼,并保证该组中存在一条这样重量的鳗鱼。
输出
对于每个操作,输出单个整数,表示该操作后该组鳗鱼的危险程度。
示例
输入 #1
2 + 1 - 1
输出 #1
0 0
输入 #2
4 + 1 + 3 + 7 - 3
输出 #2
0 0 1 0
输入 #3
9 + 2 + 2 + 12 - 2 - 2 + 4 + 1 + 1 - 12
输出 #3
0 1 1 0 0 0 0 3 2
注意
在第三个示例中,执行完所有操作后,鳗鱼集看起来像 $$$\{1, 1, 4\}$$$。对于这组鳗鱼,如果将它们全部放入一个水族箱中,则有几种可能的情况:
- 重量为 4 的鳗鱼吃掉重量为 1 的鳗鱼,然后吃掉第二条重量为 1 的鳗鱼。在这种情况下,所有战斗都没有危险。
- 重量1的鳗鱼吃掉重量1的鳗鱼,这场战斗很危险。现在水族箱里有两条鳗鱼,它们的重量分别是4和2。大的吃小的,这场战斗也很危险。在这种情况下,危险战斗的总数将为2。
因此,这组鳗鱼的危险度为2。