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>
int n, a[1111111], b[1111111];
std::set<int> S;
long long ans[1111111];
namespace segt {
int stk[10222222], s[10222222][2], sz[10222222], tc = 5e5, tp;
long long sm[10222222];
int nd() {
  if (tp) {
    int a = stk[tp];
    tp--, s[a][0] = s[a][1] = sz[a] = sm[a] = 0;
    return a;
  } else
    return ++tc;
}
void pushu(int p) {
  sz[p] = sz[s[p][0]] + sz[s[p][1]], sm[p] = sm[s[p][0]] + sm[s[p][1]];
}
void ins(int v, int p, int pl = 1, int pr = 4e5) {
  if (pl == pr) {
    sz[p] = 1, sm[p] = v;
    return;
  }
  if (!s[p][0]) s[p][0] = nd(), s[p][1] = nd();
  int pm = (pl + pr) >> 1, dr = v > pm;
  dr ? pl = pm + 1 : pr = pm, ins(v, s[p][dr], pl, pr), pushu(p);
}
long long lins(int v, int p, int pl = 1, int pr = 4e5) {
  if (pl == pr) {
    sz[p] = 1, sm[p] = v;
    return 0;
  }
  if (!s[p][0]) s[p][0] = nd(), s[p][1] = nd();
  int pm = (pl + pr) >> 1, dr = v > pm;
  long long r;
  dr ? pl = pm + 1 : pr = pm, r = lins(v, s[p][dr], pl, pr), pushu(p);
  if (dr) r += v * 1ll * sz[s[p][0]] - sm[s[p][0]];
  return r;
}
long long rins(int v, int p, int pl = 1, int pr = 4e5) {
  if (pl == pr) {
    sz[p] = 1, sm[p] = v;
    return 0;
  }
  if (!s[p][0]) s[p][0] = nd(), s[p][1] = nd();
  int pm = (pl + pr) >> 1, dr = v > pm;
  long long r;
  dr ? pl = pm + 1 : pr = pm, r = rins(v, s[p][dr], pl, pr), pushu(p);
  if (!dr) r += sm[s[p][1]] - v * 1ll * sz[s[p][1]];
  return r;
}
void reuse(int p) {
  if (s[p][0]) reuse(s[p][0]);
  if (s[p][1]) reuse(s[p][1]);
  stk[++tp] = p;
}
}  // namespace segt
bool dec(int x, int y) { return x > y; }
int L[1111111], R[1111111], tp[1111111], rt[1111111];
long long merge(int l, int m, int r) {
  register int i;
  long long ret = 0;
  if (m - l > r - m) {
    segt::reuse(rt[m + 1]);
    std::sort(tp + m + 1, tp + r + 1, dec);
    for (i = m + 1; i <= r; i++) ret += segt::lins(tp[i], rt[l]);
  } else {
    segt::reuse(rt[l]);
    std::sort(tp + l, tp + m + 1, dec);
    rt[l] = rt[m + 1];
    for (i = m; i >= l; i--) ret += segt::rins(tp[i], rt[l]);
  }
  L[l] = r, R[r] = l;
  return ret;
}
long long push(int x, int v) {
  L[x] = R[x] = x, segt::ins(v, x), tp[x] = v;
  long long r = 0;
  if (R[x - 1]) r += merge(R[x - 1], x - 1, x);
  if (L[x + 1]) r += merge(R[x], x, L[x + 1]);
  return r;
}
int main() {
  register int i;
  for (i = 1; i <= 400000; i++) S.insert(i), rt[i] = i;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    scanf("%d%d", a + i, b + i);
    int da = *S.lower_bound(a[i]);
    ans[i] = b[i] * 1ll * (da - a[i]), S.erase(da), a[i] = da;
  }
  long long V = 0;
  for (i = 1; i <= n; i++) V += ans[i] - push(a[i], b[i]), printf("%lld\n", V);
}
