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;
int n, m;
int A[200006], B[200006];
long long as = 0;
struct tcurts {
  int l, r, o;
  tcurts() : l(0), r(0), o(0) {}
  tcurts(int l, int r, int o) : l(l), r(r), o(o) {}
  bool operator<(const tcurts x) const { return r < x.r; }
};
set<tcurts> W;
int rt[200006], ts[200006], cr;
long long st[200006], sb[200006];
int ls[200006 * 20], rs[200006 * 20], s[200006 * 20], cnt;
long long T[200006 * 20], S[200006 * 20];
void pu(int rt) {
  T[rt] = T[rs[rt]] + T[ls[rt]] + s[rs[rt]] * S[ls[rt]];
  S[rt] = S[ls[rt]] + S[rs[rt]];
  s[rt] = s[ls[rt]] + s[rs[rt]];
}
void gt(int& rt, int l, int r, int p) {
  if (!rt) rt = ++cnt;
  if (l == r) {
    T[rt] = 0, S[rt] = l, s[rt] = 1;
    return;
  }
  int m = l + r >> 1;
  if (p <= m)
    gt(ls[rt], l, m, p);
  else
    gt(rs[rt], m + 1, r, p);
  pu(rt);
}
void merge(int& u, int v, int l, int r) {
  if (!u || !v) {
    u = u | v;
    return;
  }
  int m = l + r >> 1;
  merge(ls[u], ls[v], l, m), merge(rs[u], rs[v], m + 1, r);
  pu(u);
}
long long gas(int x) { return T[rt[x]] + sb[x] * ts[x] - st[x]; }
void wkr(int a, int b) {
  auto t = W.lower_bound(tcurts(0, a - 1, 0));
  int tl, tr, dx;
  if (t == W.end() || (t->l) > a) {
    tl = tr = a;
    ++cr;
    gt(rt[cr], 1, n, b);
    dx = cr;
    ts[dx] = a;
  } else {
    dx = t->o;
    as -= gas(dx);
    gt(rt[dx], 1, n, b);
    tl = t->l, tr = (t->r) + 1;
    W.erase(t);
  }
  st[dx] += a * 1ll * b;
  sb[dx] += b;
  t = W.lower_bound(tcurts(0, tr + 1, 0));
  if (t != W.end() && t->l == tr + 1) {
    int px = t->o;
    as -= gas(px);
    merge(rt[dx], rt[px], 1, n);
    st[dx] += st[px], sb[dx] += sb[px];
    tr = t->r;
    W.erase(t);
  }
  as += gas(dx);
  W.insert(tcurts(tl, tr, dx));
}
void solve() {
  cin >> n;
  for (int i = (1), iend = (n); i <= iend; ++i) scanf("%d%d", A + i, B + i);
  for (int i = (1), iend = (n); i <= iend; ++i) {
    wkr(A[i], B[i]);
    printf("%lld\n", as);
  }
}
signed main() { solve(); }
