Problem Description

Farmer John's pasture can be seen as a huge two-dimensional grid made of square cells (imagine a huge chessboard). Initially, the pasture is empty.

Farmer John will add $N$ cows ($1\le N\le 10^5$) to the pasture one by one. The $i$-th cow will occupy the cell $(x_i,y_i)$, which is different from all cells already occupied by other cows ($0\le x_i,y_i\le 1000$).

A cow is called "comfortable" if it has exactly three other cows adjacent to it horizontally or vertically. Farmer John is interested in the number of comfortable cows on his farm. For each $i$ from $1\ldots N$, output the number of comfortable cows after the $i$-th cow is added to the pasture.

Input Format

The first line contains an integer $N$. The next $N$ lines each contain two space-separated integers, representing the coordinates $(x,y)$ of a cow's cell. The input guarantees that all cell coordinates are distinct.

Output Format

On line $i$, output the number of comfortable cows after the first $i$ cows have been added to the pasture.

8
0 1
1 0
1 1
1 2
2 1
2 2
3 1
3 2

0
0
0
1
0
0
1
2

Hint

Sample Explanation 1

After the first four cows are added, the cow at $(1,1)$ is comfortable.

After the first seven cows are added, the cow at $(2,1)$ is comfortable.

After the first eight cows are added, the cows at $(2,1)$ and $(2,2)$ are comfortable.

Test Point Properties

• Test points $1-4$ satisfy $N\le 400$.
• Test points $5-12$ have no additional constraints.

Translated by ChatGPT 5