当前没有测试数据。

题目描述

某地区可以被视为一个巨大的二维平面网格。初始时，该地区没有任何信号塔。

通信公司计划依次建设 $N$ 座信号塔。第 $i$ 座信号塔将建立在坐标 $(x_i, y_i)$ 处，且保证该位置之前没有其他信号塔。

如果一座信号塔在水平或竖直方向上恰好与三座其他信号塔相邻（即该信号塔上下左右四个相邻的方向中有三个位置有信号塔）则被称为 "过载塔"。

由于"过载塔"会影响通信稳定性，公司决定额外建设一些信号塔，直到没有任何信号塔（包括新建的）是"过载塔"为止。新建的信号塔坐标可以是任意整数坐标，不限于 $0 \cdots 1000$ 范围内（即：坐标可以是负数）。

对于 $i = 1 \cdots N$ 的每座信号塔，请编程计算出：当初始已建设了前 $i$ 座信号塔后，为达成目标所需最少额外建设的信号塔最少数量。

输入格式

输入的第一行包含一个整数 $N$。

接下来 $N$ 行每行包含两个空格分隔的整数，表示第 $i$ 座信号塔的坐标 $(x_i, y_i)$。

输出格式

输出 $N$ 行，对于 $1 \cdots N$ 中的每个 $i$，输出一行，为需要额外建设的最少信号塔数量。

样例 #1

输入

9
0 1
1 0
1 1
1 2
2 1
2 2
3 1
3 2
4 1

输出

0
0
0
1
0
0
1
2
4

样例 #2

输入

10
1 1
1 2
2 1
2 2
3 2
1 3
3 1
0 2
2 3
4 2

输出

0
0
0
0
1
2
3
2
1
3

样例说明

样例 1 说明

当只有 $1 \sim 3$ 个信号塔时，肯定不可能出现"过载塔"，结果一定是 $0$。

对于 $i = 4$，需要在 $(2, 1)$ 添加一座信号塔使得位于 $(1, 1)$ 的信号塔不再过载。

对于 $i = 9$，最优方案是在 $(2, 0)$、$(3, 0)$、$(2, -1)$ 和 $(2, 3)$ 添加信号塔。

数据范围

对于 $100\%$ 的数据，满足 $1 \le N \le 10^5$，坐标范围为 $0 \le x_i, y_i \le 1000$。

请注意：新建塔的位置不受输入范围限制，坐标可以是任意整数。