Monocarp 正在召集一支军队在电子游戏中与一条龙作战。
军队由两部分组成:英雄和防御神器。每个英雄都有一个参数——他的生命值。每件防御神器还有一个参数——耐用性。
在战斗开始之前,Monocarp会向英雄分发神器,以便每个英雄最多获得一件神器。
战斗由如下回合组成:
- 首先,龙对每个英雄造成等于 $$$\frac{1}{a + b}$$$(未经四舍五入的实数)的伤害,其中 $$$a$$$ 是存活英雄的数量,$$$b$$$ 是活动神器的数量;
- 之后,所有生命值为 $$$0$$$ 或更少的英雄死亡;
- 最后,一些工件被停用。当发生以下其中一种情况时,具有耐久度 $$$x$$$ 的神器将被停用:持有该神器的英雄死亡或受到 $$$x$$$ 总伤害(从战斗开始)。如果一件神器没有被任何英雄持有,那么它从战斗开始时就处于非活动状态。
当没有英雄活着时,战斗结束。
最初,军队是空的。有 $$$q$$$ 查询:向军队添加生命值 $$$x$$$ 的英雄或耐久性 $$$y$$$ 的神器。每次查询后,确定 Monocarp 在最佳分配工件的情况下可以生存的最大轮数。
输入
第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — 查询数。
在以下 $$$q$$$ 行的第 $$$i$$$ 行中,有两个整数 $$$t_i$$$ 和 $$$v_i$$$ ($$$t_i \in \{1, 2\}$$$; $$$1 \le v_i \le 10^9$$$) - 查询的类型和查询参数的值。如果类型为$$$1$$$,则添加生命值为$$$v_i$$$的英雄。如果类型为$$$2$$$,则添加具有耐用性$$$v_i$$$的工件。
输出
打印 $$$q$$$ 整数。每次查询后,输出 Monocarp 在最佳分配工件的情况下可以生存的最大轮数。
示例
输入 #1
3 2 5 1 4 1 10
输出 #1
0 8 19
输入 #2
10 1 9 1 6 2 4 1 8 1 3 2 10 1 3 1 6 1 10 2 6
输出 #2
9 15 19 27 30 39 42 48 59 65
注意
让我们考虑第一个例子。
- 添加了一件耐久度为 $$$5$$$ 的神器。由于还没有英雄,战斗立即结束。
- 添加了一名生命值为 $$$4$$$ 的英雄。 Monocarp 可以给他一件耐久度为 $$$5$$$ 的神器。首先,英雄在某些回合中会受到 $$$\frac{1}{1 + 1} = \frac{1}{2}$$$ 伤害。经过 $$$8$$$ 这样的回合后,总共会造成 $$$4$$$ 伤害,英雄将会死亡,而神器将会停用。没有更多的英雄活着,所以战斗在 $$$8$$$ 回合后结束。
- 添加了一名生命值为 $$$10$$$ 的英雄。现在就让耐久度$$$5$$$的神器和这个英雄在一起吧。然后,在前 $$$12$$$ 轮中,英雄将受到 $$$12 \cdot \frac{1}{2 + 1} = 4$$$ 伤害,第一个英雄将会死亡。第二个英雄还剩 $$$6$$$ 生命值,神器有 $$$1$$$ 耐久度。现在伤害为$$$\frac{1}{2}$$$,因此在另外$$$2$$$轮后,神器将停用。第二个英雄还剩下 $$$5$$$ 生命值。再过 $$$5$$$ 轮后,第二个英雄就会死亡。因此,答案是$$$12 + 2 + 5 = 19$$$。