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;
const int maxn = 2e5 + 10;
int n, par[maxn];
long long ans;
int find(int x) {
  return !par[x] ? 0 : par[x] == x ? x : par[x] = find(par[x]);
}
int tot, rt[maxn], ls[maxn << 5], rs[maxn << 5], sz[maxn << 5];
long long sum[maxn << 5], val[maxn << 5];
void maintain(int k) {
  sz[k] = sz[ls[k]] + sz[rs[k]], sum[k] = sum[ls[k]] + sum[rs[k]],
  val[k] = val[ls[k]] + val[rs[k]] + sum[ls[k]] * sz[rs[k]];
}
void ins(int& k, int l, int r, int x) {
  if (!k) k = ++tot;
  if (l == r) {
    sum[k] = x, sz[k] = 1, val[k] = 0;
  } else {
    x <= ((l + r) >> 1) ? ins(ls[k], l, ((l + r) >> 1), x)
                        : ins(rs[k], ((l + r) >> 1) + 1, r, x),
        maintain(k);
  }
}
int merge(int x, int y) {
  if (!x || !y) return x | y;
  ls[x] = merge(ls[x], ls[y]);
  rs[x] = merge(rs[x], rs[y]);
  return maintain(x), x;
}
int main() {
  cin >> n;
  for (int i = (1), iend = (n); i <= iend; ++i) {
    int p, v;
    scanf("%d%d", &p, &v), ans -= 1ll * p * v;
    int x = find(p - 1) | find(p);
    if (!x) x = par[p] = p;
    ans -= val[rt[x]];
    ins(rt[x], 1, n, v);
    ans += val[rt[x]] + 1ll * x * v;
    int tp = x + sz[rt[x]] - 1;
    if (tp <= 200000) {
      par[tp] = x;
      int y = find(tp + 1);
      if (y) {
        ans -= val[rt[x]] + val[rt[y]] + sum[rt[y]] * (y - x);
        rt[x] = merge(rt[x], rt[y]);
        par[y] = x;
        ans += val[rt[x]];
      }
    }
    printf("%lld\n", ans);
  }
  return 0;
}
