Suppose you are given a sequence S of k pairs of integers (a_1, b_1), (a_2, b_2), ..., (a_k, b_k).

You can perform the following operations on it:

  1. Choose some position i and increase a_i by 1. That can be performed only if there exists at least one such position j that i ≠ j and a_i = a_j. The cost of this operation is b_i; 
  2. Choose some position i and decrease a_i by 1. That can be performed only if there exists at least one such position j that a_i = a_j + 1. The cost of this operation is -b_i. 



Each operation can be performed arbitrary number of times (possibly zero).

Let f(S) be minimum possible x such that there exists a sequence of operations with total cost x, after which all a_i from S are pairwise distinct. 

Now for the task itself ...

You are given a sequence P consisting of n pairs of integers (a_1, b_1), (a_2, b_2), ..., (a_n, b_n). All b_i are pairwise distinct. Let P_i be the sequence consisting of the first i pairs of P. Your task is to calculate the values of f(P_1), f(P_2), ..., f(P_n).

Input

The first line contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of pairs in sequence P.

Next n lines contain the elements of P: i-th of the next n lines contains two integers a_i and b_i (1 ≤ a_i ≤ 2 ⋅ 10^5, 1 ≤ b_i ≤ n). It is guaranteed that all values of b_i are pairwise distinct.

Output

Print n integers — the i-th number should be equal to f(P_i).

Examples

Input

5
1 1
3 3
5 5
4 2
2 4


Output

0
0
0
-5
-16


Input

4
2 4
2 3
2 2
1 1


Output

0
3
7
1
#include <bits/stdc++.h>
using namespace std;
long long par[(1 << 20)], sz[(1 << 20)], n;
long long a[(1 << 20)], b[(1 << 20)];
bool active[(1 << 20)];
long long ans = 0;
struct v {
  long long prior;
  long long sz, sum, specsum;
  long long l, r, val;
  v() { prior = rand() * rand() + rand(); }
} tr[(1 << 20)];
long long roots[(1 << 20)], szTr = 1;
long long getp(long long x) { return par[x] == x ? x : par[x] = getp(par[x]); }
void refr(long long x) {
  tr[x].sz = tr[tr[x].l].sz + 1 + tr[tr[x].r].sz;
  tr[x].sum = tr[x].val + tr[tr[x].l].sum + tr[tr[x].r].sum;
  tr[x].specsum = tr[tr[x].r].specsum + (tr[tr[x].r].sz * tr[x].val) +
                  tr[tr[x].l].specsum + tr[tr[x].l].sum * (tr[tr[x].r].sz + 1);
}
pair<int, long long> splitT(long long k, long long v) {
  if (v == 0) {
    return make_pair(0, 0);
  }
  if (tr[v].val < k) {
    pair<int, long long> c = splitT(k, tr[v].r);
    tr[v].r = c.first;
    refr(v);
    return make_pair(v, c.second);
  } else {
    pair<int, long long> c = splitT(k, tr[v].l);
    tr[v].l = c.second;
    refr(v);
    return make_pair(c.first, v);
  }
}
long long mergeT(long long v1, long long v2) {
  if (v1 == 0 || v2 == 0) {
    return v1 ^ v2;
  }
  if (tr[v1].prior > tr[v2].prior) {
    tr[v1].r = mergeT(tr[v1].r, v2);
    refr(v1);
    return v1;
  } else {
    tr[v2].l = mergeT(tr[v2].l, v1);
    refr(v2);
    return v2;
  }
}
long long mergeTs(long long v1, long long v2) {
  if (v1 == 0 || v2 == 0) {
    return v1 ^ v2;
  }
  if (tr[v1].prior > tr[v2].prior) {
    pair<int, long long> nv2 = splitT(tr[v1].val, v2);
    tr[v1].r = mergeTs(tr[v1].r, nv2.second);
    tr[v1].l = mergeTs(tr[v1].l, nv2.first);
    refr(v1);
    return v1;
  } else {
    pair<int, long long> nv1 = splitT(tr[v2].val, v1);
    tr[v2].r = mergeTs(tr[v2].r, nv1.second);
    tr[v2].l = mergeTs(tr[v2].l, nv1.first);
    refr(v2);
    return v2;
  }
}
void unionv(long long a, long long b) {
  long long p1 = getp(a), p2 = getp(b);
  if (p1 > p2) {
    swap(p1, p2);
  }
  long long len = p2 - p1;
  ans -= len * (tr[roots[p2]].sum);
  par[p2] = p1;
  ans -= tr[roots[p1]].specsum;
  ans -= tr[roots[p2]].specsum;
  roots[p1] = mergeTs(roots[p1], roots[p2]);
  ans += tr[roots[p1]].specsum;
}
long long createV(long long val) {
  long long x = szTr++;
  tr[x].val = val;
  tr[x].sz = 1;
  tr[x].sum = val;
  tr[x].specsum = 0;
  return x;
}
void printTr(long long v) {
  if (v == 0) {
    return;
  }
  printTr(tr[v].l);
  cout << tr[v].val << " ";
  printTr(tr[v].r);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  for (long long i = 0; i < (1 << 20); i++) {
    par[i] = i;
  }
  cin >> n;
  for (long long i = 0; i < n; i++) {
    cin >> a[i] >> b[i];
    if (active[a[i]]) {
      long long x = createV(b[i]);
      int to = getp(a[i]);
      ans -= (a[i] - to) * b[i];
      ans -= tr[roots[to]].specsum;
      roots[to] = mergeTs(x, roots[to]);
      ans += tr[roots[to]].specsum;
      int l = a[i], r = (1 << 20);
      int m = (l + r) / 2;
      for (; l + 1 < r; m = (l + r) / 2) {
        if (getp(m) == to) {
          l = m;
        } else {
          r = m;
        }
      }
      active[r] = 1;
      unionv(r, to);
      if (active[r + 1]) {
        unionv(to, r + 1);
      }
    } else {
      roots[a[i]] = createV(b[i]);
      active[a[i]] = 1;
      if (active[a[i] + 1]) {
        unionv(a[i], a[i] + 1);
      }
      if (active[a[i] - 1]) {
        unionv(a[i], a[i] - 1);
      }
    }
    cout << ans << "\n";
  }
  return 0;
}
