题目描述

考虑无限网格。一个无限的 $2\times 2$ 方块集合称为覆盖集合，如果平面上每个单位格恰好被一个方块覆盖，且所有单位格都被覆盖。

一个方块集合称为好的，如果它是某个覆盖集合的子集。

初始时集合 $S$ 为空，有 $n$ 次操作，每次添加或删除一个方块 $(x_i,y_i)$。该方块覆盖四个单位格：

若当前该方块已在 $S$ 中，则本次操作删除它；否则加入它。每次操作后，输出 $S$ 的最大好子集大小。

输入格式

第一行输入整数 $n$，表示操作次数，$1\le n\le 200000$。

接下来 $n$ 行，每行两个整数 $x_i,y_i$，满足 $1\le x_i,y_i\le 10^9$。

输出格式

输出 $n$ 行，第 $i$ 行表示执行前 $i$ 次操作后，集合 $S$ 的最大好子集大小。

样例

输入
5
1 1
2 2
3 3
4 4
1 1

输出
1
1
2
2
2