掉落的方块

题目描述

在二维平面上的 $x$ 轴上，放置着 $n$ 个方块。给你一个二维整数数组 $positions$ ，其中$positions[i] = [left_i,sideLength_i]$ 表示：第 $i$ 个方块边长为 $sideLength_i$ ，其左侧边与$x$ 轴上坐标点 $left_i$ 对齐。 每个方块都从无穷高处掉下。方块沿 $y$ 轴负方向下落，直到着陆到另一个正方形的顶边或者是 $x$ 轴上。一个方块仅仅是擦过另一个方块的左侧边或右侧边不算着陆。一旦着陆，它就会固定在原地，无法移动。 在每个方块掉落后，回答目前所有已经落稳的方块堆叠的最高高度。

输入格式

第一行包含一个正整数$n$，表示方块数量。 接下来n行，每行包含两个整数 $left_i$和$sideLength_i$。

数据范围: $sideLength_i ≤ 10^6, left_i ≤ 10^8, n ≤ 10^5$

输出格式

对于每个方块输出一个整数$h$，表示该方块堆叠最高高度，每个答案占一行

样例 #1

样例输入 #1

3
1 2
2 3
6 1

样例输出 #1

2
5
5

提示