小熊猫来城里迎接它们的亲戚蓝熊猫了!该城镇由数轴建模。
熊猫们已经计划好了他们的聚会,但日程安排不断变化。您将获得 x t c 形式的 $$$q$$$ 更新。
- 如果 $$$c < 0$$$,则意味着 $$$|c|$$$ 更多小熊猫在位置 $$$x$$$ 和时间 $$$t$$$ 处进入数轴。然后,在每个单位时间内,他们可以各自独立地在数轴上的任一方向上移动一个单位,或者根本不移动。
- 如果 $$$c > 0$$$,则意味着 $$$c$$$ 更多蓝熊猫在 $$$t$$$ 时刻检查红熊猫的 $$$x$$$ 位置。如果蓝熊猫在特定的地点和时间没有遇到红熊猫,它们就会沮丧地立即离开数轴。如果在某个位置上有一只红熊猫,同时有一只蓝熊猫检查该位置,则它们会形成友谊并离开数轴。每只小熊猫最多可以与一只蓝熊猫建立友谊,反之亦然。
更新将按非递减 $$$x$$$ 值的顺序给出。每次更新后,如果小熊猫根据上面输入(包括)此更新中给出的所有更新以最佳顺序移动,请打印最大友谊数。
小熊猫的移动顺序可能会在更新之间发生变化。
输入
第一行包含 $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) – 更新次数。
接下来的 $$$q$$$ 行中的第 $$$i$$$ 行由 $$$3$$$ 整数 $$$x_i$$$、$$$t_i$$$ 和 $$$c_i$$$ ($$$0 \leq x_i \leq 10^9$$$, $$$0 \leq t_i \leq 组成10^9$$$, $$$0 < |c_i| \leq 1000$$$) – 第 $$$i$$$ 次更新的描述。
保证 $$$x_i$$$ 将以非降序给出。
输出
每次更新后,打印可以形成的最大好友数量。
示例
输入 #1
5 0 6 3 4 2 -5 7 4 -6 10 5 100 10 8 7
输出 #1
0 3 3 3 10
输入 #2
5 0 6 3 4 2 -5 7 4 -6 10 5 100 11 8 7
输出 #2
0 3 3 3 9
输入 #3
7 0 8 6 2 7 -2 3 1 -6 5 3 -8 7 3 -3 8 0 -2 8 2 1
输出 #3
0 0 6 6 6 6 7
输入#4
4 0 0 -3 0 0 2 0 0 4 0 0 -10
输出#4
0 2 3 6
注意
在第一个示例中,每次更新后的好友数量可以优化如下:
1. $$$3$$$ 蓝熊猫现在在 $$$6$$$ 位置检查位置 $$$0$$$ 的红熊猫。哪里都没有小熊猫,所以也就没有友谊。
2. $$$5$$$小熊猫现在出现在位置$$$4$$$,时间$$$2$$$。 $$$4$$$ 的红熊猫可以在 $$$6$$$ 时间前往位置 $$$0$$$,其中 $$$3$$$ 可以与 $$$3$$$ 现有的蓝熊猫建立友谊。
3. $$$6$$$小熊猫现在出现在位置$$$7$$$,时间$$$4$$$。没有添加新的蓝色熊猫,因此最大好友数量仍然是$$$3$$$。
4. $$$100$$$蓝色熊猫现在出现在位置$$$10$$$,时间$$$5$$$。没有小熊猫可以在 $$$5$$$ 时联系到他们,因此不会创建新的友谊。
5. $$$7$$$蓝色熊猫现在出现在位置$$$10$$$,时间$$$8$$$。 $$$6$$$ 位置 $$$7$$$ 和时间 $$$4$$$ 的红熊猫,以及 $$$1$$$ 位置 $$$4$$$ 和时间 $$$2$$$ 的红熊猫,可以到达 $$$7$$$ 位置 $$$10$$$ 的蓝熊猫,时间 $$$8$$$,增加 $$$7$$$ 新友谊。这使得友谊总数达到 $$$10$$$。