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;
#pragma pack(push, 1)
struct w {
  int a;
  long long b;
  int l, r;
  w(int aa, long long bb, int ll, int rr) : a(aa), b(bb), l(ll), r(rr) {}
  bool leave() { return l == 0 && r == 0; }
};
#pragma pack(pop)
int n;
int par[400005], l[400005], r[400005];
vector<w> v[400005];
long long ans;
bool lr;
int ta, tb, tc;
int find(int a) { return par[a] == a ? a : par[a] = find(par[a]); }
inline pair<int, long long> add(int a, int b) {
  int at = 0;
  pair<int, long long> re(0, 0);
  for (int i = 17; i >= 0; i--) {
    v[a][at].a++;
    v[a][at].b += b;
    if (b & (1 << i)) {
      if (!v[a][at].r) {
        v[a][at].r = v[a].size();
        v[a].emplace_back(0, 0, 0, 0);
      }
      at = v[a][at].r;
    } else {
      int to = v[a][at].r;
      if (to) {
        re.first += v[a][to].a;
        re.second += v[a][to].b;
      }
      if (!v[a][at].l) {
        v[a][at].l = v[a].size();
        v[a].emplace_back(0, 0, 0, 0);
      }
      at = v[a][at].l;
    }
  }
  v[a][at].a++;
  v[a][at].b += b;
  return re;
}
void dfs(int a, int b, int c) {
  if (v[a][b].leave()) {
    auto p = add(tc, v[a][b].b);
    if (lr) {
      l[tc]--;
      ans += (long long)((l[tc] + p.first) - (r[a] - c)) * v[a][b].b - p.second;
    } else {
      r[tc]++;
      ans += (long long)((l[tc] + p.first) - (r[a] - c)) * v[a][b].b +
             (v[tc][0].b - v[a][b].b - p.second);
    }
    return;
  }
  if (v[a][b].l) {
    dfs(a, v[a][b].l, c);
    c += v[a][v[a][b].l].a;
  }
  if (v[a][b].r) dfs(a, v[a][b].r, c);
}
void merge(int a, int b) {
  a = find(a);
  b = find(b);
  lr = r[a] - l[a] < r[b] - l[b];
  if (lr) {
    tc = b;
    dfs(a, 0, 0);
    v[a].clear();
    par[a] = b;
  } else {
    tc = a;
    dfs(b, 0, 0);
    v[b].clear();
    par[b] = a;
  }
}
int main() {
  scanf("%d", &n);
  while (n--) {
    scanf("%d%d", &ta, &tb);
    if (par[ta]) {
      ans += (long long)tb * (r[find(ta)] + 1 - ta);
      ta = r[par[ta]] + 1;
    }
    par[ta] = ta;
    l[ta] = ta;
    r[ta] = ta;
    v[ta].emplace_back(0, 0, 0, 0);
    add(ta, tb);
    if (par[l[ta] - 1]) merge(l[ta] - 1, ta);
    if (par[r[find(ta)] + 1]) merge(ta, r[par[ta]] + 1);
    printf("%lld\n", ans);
  }
  return 0;
}
