Counting New Holes in a Simplified Tetris Game

DanDan, an avid Tetris enthusiast, has grown tired of scoring endlessly. She has now devised a simplified version of Tetris. Initially, the ground is empty. All blocks are axis‐aligned rectangles that cannot be rotated or flipped. At each move, DanDan chooses a horizontal position and drops a block. As the block falls, it stops immediately when it touches the ground or an already placed block. When landing on another block, the rule is that the bottom edge of the falling block must have a non‐zero length segment (i.e. more than just a point) that coincides with the top edge of the block it lands on (see Figure 1).

A hole is defined as a closed region of positive area whose boundary consists of block edges and/or the ground (see Figures 2(a) and 2(b)). In order to keep the configuration "beautiful", DanDan wonders, for each block drop, how many new holes are formed.

Note: If two blocks are tightly adjacent (as in Figure 3), then when a new block falls, it does not form a new hole even if it touches both, because their touching boundaries merge.

You are given the height H_i and the left and right boundaries L_i and R_i (with 1 \le i \le n) for each dropped block. After each block is dropped, determine the number of new holes created.

The block falling process is simulated as follows:

• The falling block, with horizontal interval \([L_i, R_i]\) and height \(H_i\), falls until its bottom edge reaches a landing level \(Y\).
• The landing level \(Y\) is determined by the maximal top among all previously placed blocks that have a non‐zero overlapping interval with \([L_i, R_i]\), or the ground (at \(Y=0\)) if no such block exists. Formally, if a block spanning \([L_j, R_j]\) with top \(Y_j = y_j + H_j\) satisfies
  
  \(\text{intersection length} = \max(0, \min(R_i, R_j) - \max(L_i, L_j))>0\),
  then \(Y_j\) is a candidate. Let
  
  \(Y = \max\Big(0, \{Y_j \text{ such that block } j \text{ is a candidate}\}\Big).\)
• Then, the falling block’s bottom edge will have contact intervals with the supports that have top exactly equal to \(Y\). In particular, if \(Y = 0\) (ground) then the entire base \([L_i,R_i]\) is considered in contact; otherwise, for each block \(j\) with \(Y_j = Y\) and a nonzero intersection with \([L_i,R_i]\), the contact interval is \([\max(L_i, L_j), \min(R_i,R_j)]\).
• After merging these contact intervals (i.e. taking their union), any gap in the interval \([L_i,R_i]\) (including gaps at the left and right boundaries) becomes a new hole.

For example, consider the following drops:

Example 1:

Input:
3
3 1 4
2 2 5
1 0 6
Explanation:
Block 1: drops with H=3, L=1, R=4. Lands on ground (Y=0) → Contact = [1,4]. Holes = 0.
Block 2: H=2, L=2, R=5. Overlaps with Block 1 on [2,4] (Block 1 top = 3) so lands at Y=3 → Contact = [2,4]; gap from 4 to 5 yields 1 new hole.
Block 3: H=1, L=0, R=6. Overlaps with Block 1 ([1,4], top=3) and Block 2 ([2,5], top=5). Maximum landing level Y=5 comes from Block 2 → Contact = [2,5]; gaps [0,2] and [5,6] yield 2 new holes.
Output:
0
1
2

</p>

Input Format: The first line contains an integer \(n\) (the number of blocks). Each of the following \(n\) lines contains three integers: \(H_i\), \(L_i\), and \(R_i\), separated by spaces.

Output Format: Output \(n\) lines. The \(i\)th line should contain a single integer representing the number of new holes formed right after the \(i\)th block is dropped.

Note: All formulas are written in LaTeX format.

inputFormat

The first line contains a single integer \(n\) (number of blocks). Each of the next \(n\) lines contains three space-separated integers \(H_i\), \(L_i\), and \(R_i\) where \(H_i\) is the height of the block, and \([L_i, R_i]\) is its horizontal span.

outputFormat

Output \(n\) lines, each containing a single integer: the number of new holes formed immediately after dropping the corresponding block.

sample

3
3 1 4
2 2 5
1 0 6

0
1
2

</p>