Extending Set of Points
Description
For a given set of two-dimensional points $S$, let's denote its extension $E(S)$ as the result of the following algorithm:
Create another set of two-dimensional points $R$, which is initially equal to $S$. Then, while there exist four numbers $x_1$, $y_1$, $x_2$ and $y_2$ such that $(x_1, y_1) \in R$, $(x_1, y_2) \in R$, $(x_2, y_1) \in R$ and $(x_2, y_2) \notin R$, add $(x_2, y_2)$ to $R$. When it is impossible to find such four integers, let $R$ be the result of the algorithm.
Now for the problem itself. You are given a set of two-dimensional points $S$, which is initially empty. You have to process two types of queries: add some point to $S$, or remove some point from it. After each query you have to compute the size of $E(S)$.
The first line contains one integer $q$ ($1 \le q \le 3 \cdot 10^5$) — the number of queries.
Then $q$ lines follow, each containing two integers $x_i$, $y_i$ ($1 \le x_i, y_i \le 3 \cdot 10^5$), denoting $i$-th query as follows: if $(x_i, y_i) \in S$, erase it from $S$, otherwise insert $(x_i, y_i)$ into $S$.
Print $q$ integers. $i$-th integer should be equal to the size of $E(S)$ after processing first $i$ queries.
Input
The first line contains one integer $q$ ($1 \le q \le 3 \cdot 10^5$) — the number of queries.
Then $q$ lines follow, each containing two integers $x_i$, $y_i$ ($1 \le x_i, y_i \le 3 \cdot 10^5$), denoting $i$-th query as follows: if $(x_i, y_i) \in S$, erase it from $S$, otherwise insert $(x_i, y_i)$ into $S$.
Output
Print $q$ integers. $i$-th integer should be equal to the size of $E(S)$ after processing first $i$ queries.
Samples
7
1 1
1 2
2 1
2 2
1 2
1 3
2 1
1 2 4 4 4 6 3