Problem: 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) ∈ R, (x_1, y_2) ∈ R, (x_2, y_1) ∈ R and (x_2, y_2) ∉ 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).

Input

The first line contains one integer q (1 ≤ q ≤ 3 ⋅ 10^5) — the number of queries.

Then q lines follow, each containing two integers x_i, y_i (1 ≤ x_i, y_i ≤ 3 ⋅ 10^5), denoting i-th query as follows: if (x_i, y_i) ∈ 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.

Example

Input


7
1 1
1 2
2 1
2 2
1 2
1 3
2 1


Output


1 2 4 4 4 6 3 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
const int MAXN = 1e6 + 10;
const double eps = 1e-8;
const int inf = 1e9;
using namespace std;
struct edge {
  int t, v;
  edge *next;
} e[MAXN << 1], *h[MAXN], *o = e;
void add(int x, int y, int vul) {
  o->t = y;
  o->v = vul;
  o->next = h[x];
  h[x] = o++;
}
long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return x * f;
}
vector<int> vec;
int n, sz;
typedef struct node {
  int x, y;
} node;
node d[MAXN];
long long ans;
int pre[MAXN], ch[MAXN][2], res[MAXN], minn[MAXN], size[MAXN], size1[MAXN],
    size2[MAXN], size3[MAXN], key[MAXN], pos[MAXN];
bool rt[MAXN];
void newnode(int id, int vul) {
  pos[id] = id;
  pre[id] = ch[id][0] = ch[id][1] = res[id] = 0;
  rt[id] = 1;
  minn[id] = key[id] = vul;
  size[id] = 0;
  size1[id] = 0;
  size2[id] = size3[id] = 0;
  if (id >= 1 && id <= 2 * sz) size[id] = 1;
  if (id > sz && id <= 2 * sz) size2[id] = 1;
}
void reverse(int r) {
  if (!r) return;
  swap(ch[r][0], ch[r][1]);
  res[r] ^= 1;
}
void push(int x) {
  if (res[x]) {
    reverse(ch[x][0]);
    reverse(ch[x][1]);
    res[x] ^= 1;
  }
}
int pd1(int id) {
  if (id >= 1 && id <= 2 * sz) return 1;
  return 0;
}
int pd2(int id) {
  if (id > sz && id <= 2 * sz) return 1;
  return 0;
}
void up(int x) {
  minn[x] = key[x];
  pos[x] = x;
  if (ch[x][0] && minn[ch[x][0]] < minn[x])
    minn[x] = minn[ch[x][0]], pos[x] = pos[ch[x][0]];
  if (ch[x][1] && minn[ch[x][1]] < minn[x])
    minn[x] = minn[ch[x][1]], pos[x] = pos[ch[x][1]];
  size[x] = size[ch[x][0]] + size[ch[x][1]] + size1[x] + pd1(x);
  size2[x] = size2[ch[x][0]] + size2[ch[x][1]] + pd2(x) + size3[x];
}
void P(int x) {
  if (!rt[x]) P(pre[x]);
  push(x);
}
void rotate(int x, int kind) {
  int y = pre[x];
  pre[ch[x][kind]] = y;
  ch[y][!kind] = ch[x][kind];
  if (rt[y])
    rt[x] = 1, rt[y] = 0;
  else
    ch[pre[y]][ch[pre[y]][1] == y] = x;
  pre[x] = pre[y];
  ch[x][kind] = y;
  pre[y] = x;
  up(y);
}
void splay(int x) {
  P(x);
  while (!rt[x]) {
    if (rt[pre[x]])
      rotate(x, ch[pre[x]][0] == x);
    else {
      int y = pre[x];
      int kind = ch[pre[y]][0] == y;
      if (ch[y][kind] == x)
        rotate(x, !kind), rotate(x, kind);
      else
        rotate(y, kind), rotate(x, kind);
    }
  }
  up(x);
}
void access(int x) {
  int y = 0;
  while (x) {
    splay(x);
    if (ch[x][1])
      size1[x] += size[ch[x][1]], size3[x] += size2[ch[x][1]],
          pre[ch[x][1]] = x, rt[ch[x][1]] = 1;
    if (y) rt[y] = 0, size1[x] -= size[y], size3[x] -= size2[y];
    ch[x][1] = y;
    up(x);
    y = x;
    x = pre[x];
  }
}
void mroot(int x) {
  access(x);
  splay(x);
  reverse(x);
}
void Link(int x, int y) {
  mroot(x);
  mroot(y);
  ans -= 1ll * size2[x] * (size[x] - size2[x]);
  ans -= 1ll * size2[y] * (size[y] - size2[y]);
  pre[x] = y;
  size[y] += size[x];
  size1[y] += size[x];
  size2[y] += size2[x];
  size3[y] += size2[x];
  ans += 1ll * size2[y] * (size[y] - size2[y]);
}
void destory(int x, int y, int z) {
  mroot(x);
  access(z);
  splay(y);
  ans -= 1ll * size2[y] * (size[y] - size2[y]);
  ch[y][0] = ch[y][1] = 0;
  pre[x] = pre[z] = 0;
  rt[x] = rt[z] = 1;
  up(x);
  up(y);
  up(z);
  ans += 1ll * size2[x] * (size[x] - size2[x]);
  ans += 1ll * size2[z] * (size[z] - size2[z]);
}
bool pd(int x, int y) {
  while (pre[x]) x = pre[x];
  while (pre[y]) y = pre[y];
  return x == y;
}
int Minn(int x, int y) {
  mroot(x);
  access(y);
  splay(y);
  return pos[y];
}
typedef struct Node {
  int x, y, z;
  friend bool operator<(Node aa, Node bb) {
    if (aa.x == bb.x && aa.y == bb.y) return aa.z < bb.z;
    if (aa.x == bb.x) return aa.y < bb.y;
    return aa.x < bb.x;
  }
} Node;
set<Node> s;
set<Node>::iterator ite, ip;
bool check(int x, int y) {
  ite = s.lower_bound((Node){x, y, 0});
  if (ite == s.end()) return 0;
  if (ite->x == x && ite->y == y) return 1;
  return 0;
}
int last[MAXN];
pair<int, int> Edge[MAXN];
int vis[MAXN];
int main() {
  n = read();
  for (int i = 1; i <= n; i++)
    d[i].x = read(), d[i].y = read(), vec.push_back(d[i].x),
    vec.push_back(d[i].y);
  sort(vec.begin(), vec.end());
  sz = unique(vec.begin(), vec.end()) - vec.begin();
  for (int i = 1; i <= n; i++) {
    d[i].x =
        lower_bound(vec.begin(), vec.begin() + sz, d[i].x) - vec.begin() + 1;
    d[i].y =
        lower_bound(vec.begin(), vec.begin() + sz, d[i].y) - vec.begin() + 1;
  }
  for (int i = n; i >= 1; i--) {
    if (check(d[i].x, d[i].y)) {
      ite = s.lower_bound((Node){d[i].x, d[i].y, 0});
      last[i] = ite->z;
      s.erase(ite);
    } else
      last[i] = inf;
    s.insert((Node){d[i].x, d[i].y, i});
  }
  for (int i = 1; i <= n; i++) {
    if (last[i] <= n) vis[last[i]] = vis[i] ^ 1;
  }
  s.clear();
  for (int i = 1; i <= 2 * sz; i++) newnode(i, inf);
  int cnt = 2 * sz;
  for (int i = 1; i <= n; i++) {
    int x = d[i].x;
    int y = d[i].y + sz;
    if (check(x, y)) {
      ite = s.lower_bound((Node){x, y, 0});
      destory(ite->x, ite->z, ite->y);
      s.erase(ite);
    } else {
      if (vis[i]) {
        printf(" %lld", ans);
        continue;
      }
      if (pd(x, y)) {
        int t1 = Minn(x, y);
        if (key[t1] < last[i]) {
          int tt1 = Edge[t1 - 2 * sz].first;
          int tt2 = Edge[t1 - 2 * sz].second;
          s.erase(s.lower_bound((Node){tt1, tt2, t1}));
          destory(tt1, t1, tt2);
          cnt++;
          Edge[cnt - 2 * sz] = make_pair(x, y);
          newnode(cnt, last[i]);
          Link(cnt, x);
          Link(cnt, y);
          s.insert((Node){x, y, cnt});
        }
      } else {
        cnt++;
        Edge[cnt - 2 * sz] = make_pair(x, y);
        newnode(cnt, last[i]);
        Link(cnt, x);
        Link(cnt, y);
        s.insert((Node){x, y, cnt});
      }
    }
    if (i == 1)
      printf("%lld", ans);
    else
      printf(" %lld", ans);
  }
  return 0;
}