Emotional Tetris

Time limit1sMemory limit512 MB

Summary

Given Q drops of horizontal 1x4 or vertical 4x1 blocks on a grid, count for each drop how many blocks directly or indirectly rest under it through shared faces.

Level: Hard8 of 10
Topics: Segment tree, Simulation, Implementation
Solved: No attempts yet

Introduction

Didi is playing a tetris game that uses only 1 \times 4 'ㅡ'-shaped blocks and 4 \times 1 'ㅣ'-shaped blocks. In this game, you choose the position where a block falls, and it drops straight down from there. A block cannot be moved sideways or rotated. When the bottom of a falling block touches the top of another block or the floor by even one cell, the block stops and rests on that surface.

'If this block falls, the blocks underneath will really hurt...' Didi, who plays tetris with a lot of feeling, wants to count how many blocks bear the load when a block falls. Any block that shares a face with the bottom of the falling block bears the load. Any block that shares a face with a block that bears the load also bears the load.

The kind leejseo wants to help the emotional Didi. Write a program that, each time Didi drops a block, counts how many blocks bear the load of that block. Help Didi by following leejseo's lead.

Input

The first line contains the number of blocks Didi drops, $Q$ ( $1 \le Q \le 10^5$ ).

Each of the next $Q$ lines gives one block Didi drops. Each line has one of the following two formats.

1 $a$ : Drop a 'ㅡ'-shaped block so that its left end cell is at position $a$ .
2 $a$ : Drop an 'ㅣ'-shaped block at position $a$ .

$a$ is always an integer, and no part of a block goes outside positions 1 to 400,000.

Output

For each of the $Q$ drops, print the number of blocks that bear the load of that block.

Examples2

Example 1
Input
```
6
1 5
2 5
2 6
2 7
2 8
1 5
```
Expected output
```
0
1
1
1
1
5
```

Example 2

Input

Expected output