F. Расширение множества точек
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Для заданного множества точек на координатной плоскости $$$S$$$ обозначим его расширение $$$E(S)$$$ как результат следующего алгоритма:

Создадим другое множество точек $$$R$$$, изначально равное $$$S$$$. Затем, пока существуют четыре числа $$$x_1$$$, $$$y_1$$$, $$$x_2$$$ и $$$y_2$$$, такие, что $$$(x_1, y_1) \in R$$$, $$$(x_1, y_2) \in R$$$, $$$(x_2, y_1) \in R$$$ и $$$(x_2, y_2) \notin R$$$, добавим $$$(x_2, y_2)$$$ к $$$R$$$. Когда такую четверку чисел найти будет нельзя, прекратим алгоритм и скажем, что множество $$$R$$$ — результат.

А теперь — сама задача. У вас есть множество $$$S$$$, изначально пустое. Надо обрабатывать два типа запросов: добавить какую-нибудь точку в $$$S$$$, или удалить точку. После каждого запроса выведите, чему равен размер множества $$$E(S)$$$.

Входные данные

В первой строке задано одно целое число $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — количество запросов.

Затем следуют $$$q$$$ строк, в каждой из которых записаны два целых числа $$$x_i$$$, $$$y_i$$$ ($$$1 \le x_i, y_i \le 3 \cdot 10^5$$$), обозначающих $$$i$$$-й запрос следующим образом: если $$$(x_i, y_i) \in S$$$, удалить эту точку из $$$S$$$, иначе вставить $$$(x_i, y_i)$$$ в $$$S$$$.

Выходные данные

Выведите $$$q$$$ целых чисел. $$$i$$$-е число должно быть равно размеру $$$E(S)$$$ после первых $$$i$$$ запросов.

Пример
Входные данные
7
1 1
1 2
2 1
2 2
1 2
1 3
2 1
Выходные данные
1 2 4 4 4 6 3