考虑一个无限网格。如果一个 $2 \times 2$ 正方形的无限集合能够使得平面上的每个单元格都被且仅被一个正方形覆盖，且这些正方形覆盖了整个平面，则称该集合为覆盖集（covering set）。

如果一个正方形集合是某个覆盖集的子集，则称该集合为“好”（good）的。

你拥有一个初始为空的正方形集合 $S$，以及 $n$ 个关于添加和移除正方形 $(x_i, y_i)$ 的查询。其中，数字对 $(x_i, y_i)$ 描述了一个覆盖单元格 $(x_i, y_i)$、$(x_i + 1, y_i)$、$(x_i, y_i + 1)$ 和 $(x_i + 1, y_i + 1)$ 的正方形。

在每次查询后，你需要输出一个整数，即集合 $S$ 中最大的“好”子集的大小。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 200\,000$)，表示查询次数。

接下来的 $n$ 行，每行包含两个整数 $x_i, y_i$ ($1 \le x_i, y_i \le 10^9$)。如果在第 $i$ 次查询时，由 $(x_i, y_i)$ 定义的正方形已经在 $S$ 中，则将其从集合中移除；否则，将其加入集合。

输出格式

输出 $n$ 行，第 $i$ 行输出执行前 $i$ 次查询后，集合 $S$ 中最大的“好”子集的大小。

样例

输入 1

5
1 1
2 2
3 3
4 4
1 1

输出 1

1
1
2
2
2