Farmer Eureka's pasture can be viewed as a huge 2D grid of cells (a chessboard). Initially, the pasture is empty.
Farmer Yurik adds N (\(1<=N<=10^5\)) cows to pasture one by one. ith cow will occupy the cell (xi,yi ) which is different from the cells occupied by all other cows (\(0<=x_i,y_i<=1000\)).
A cow is called "comfortable" if it has exactly three horizontal and vertical neighbors. Comfortable cows produce less milk, so Farmer Yurik wants to add cows until there are comfortable cows (including the one he will add). Note that the cows you add do not have to have x and y coordinates in the range \(0… 1000\).
For each i in the range \(1…N\), print the minimum number of cows it needs to add so that there are no comfortable cows left, assuming that only cows are in the pasture \(1…i\).
Input
The first line contains the integer
N. Each of the following
N lines contains 2 space-separated integers (
x,
y) indicating cell coordinates with a cow.
Imprint
The minimum number of cows Farmer Yurik must add, for each
i in the
\(1…N\) range, on a separate line.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
9
0 1
10
1 1
1 2
2 1
2 2
3 1
3 2
4 1 |
0
0
0
1
0
0
1
2
4 |
For i=4, Farmer Yurik must add a cow to position (2,1),
to make the cow in position (1,1) uncomfortable.
For i=9, the best Farmer can do is add cows at positions (2,0), (3,0), (2,−1), (2, 3).
|