402508: GYM100796 B Wet Boxes

Bob works in a warehouse which contains a large pile of boxes. The position of a box can be described with a pair of integers (x, y). Each box either stands on the ground (y = 0) or stands on top of two boxes with positions (x, y - 1) and (x + 1, y - 1) (see the figure).

Sometimes the contents of a box leak out and the box gets wet. When a box becomes wet, so do the two boxes below it. Given a list of boxes that leak in succession, help Bob count how many dry boxes became wet after each leak. Don't include boxes that were already wet.

The first line contains a single integer n, the number of leaking boxes (1 ≤ n ≤ 10⁵). The i-th of the next n lines contains two space-separated integers x_i and y_i, the position of the i-th leaking box (0 ≤ x_i, y_i ≤ 10⁹).

Output n lines: in the i-th line output the number of boxes that became wet after the i-th box had leaked.

4
1 3
3 2
0 6
1 1

10
3
15
0