A12558 | Extending Set of Points

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.