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 inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const long long _INF = 0xc0c0c0c0c0c0c0c0;
const long long mod = (int)1e9 + 7;
const int N = 5e6;
int n;
struct Node {
  int ls, rs, num;
  long long sum;
  Node() { ls = rs = num = sum = 0; }
} tr[N];
int tot;
void Insert(int &p, int b, int l, int r) {
  if (p == 0) p = ++tot;
  if (l == r) {
    ++tr[p].num;
    tr[p].sum = b;
    return;
  }
  int m = l + r >> 1;
  if (b <= m)
    Insert(tr[p].ls, b, l, m);
  else
    Insert(tr[p].rs, b, m + 1, r);
  tr[p].sum = tr[tr[p].ls].sum + tr[tr[p].rs].sum;
  tr[p].num = tr[tr[p].ls].num + tr[tr[p].rs].num;
}
long long ans = 0;
int Merge(int l, int r, int px, int py) {
  if (!px) return py;
  if (!py) return px;
  tr[px].num += tr[py].num;
  tr[px].sum += tr[py].sum;
  if (l != r) {
    int m = l + r >> 1;
    ans = ans - tr[tr[py].rs].sum * tr[tr[px].ls].num +
          tr[tr[px].ls].sum * tr[tr[py].rs].num;
    tr[px].ls = Merge(l, m, tr[px].ls, tr[py].ls);
    tr[px].rs = Merge(m + 1, r, tr[px].rs, tr[py].rs);
  }
  return px;
}
int pre[N];
int r[N], rt[N];
int Find(int x) {
  if (x == pre[x]) return x;
  return pre[x] = Find(pre[x]);
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i < N; ++i) {
    pre[i] = i;
    r[i] = i;
  }
  int a, b;
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d", &a, &b);
    if (rt[a] != 0) {
      int p = Find(a);
      int rr = r[p] + 1;
      ans += 1ll * b * (rr - a);
      a = rr;
    }
    Insert(rt[a], b, 1, n);
    if (rt[a - 1] != 0) {
      int lx = Find(a - 1);
      r[lx] = a;
      pre[a] = lx;
      rt[lx] = Merge(1, n, rt[lx], rt[a]);
    }
    if (rt[a + 1] != 0) {
      int rx = Find(a + 1);
      int lx = Find(a);
      r[lx] = r[rx];
      pre[rx] = lx;
      rt[lx] = Merge(1, n, rt[lx], rt[rx]);
    }
    printf("%lld\n", ans);
  }
  return 0;
}
