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 i, n, a[400005], b[400005], ch[400005][2], root[400005], fa[400005],
    siz[400005], w[400005], f[400005], s[400005], l[400005], r[400005], k;
long long ans, sum[400005], sb[400005], sizb[400005];
void pushup(int i) {
  siz[i] = siz[ch[i][0]] + siz[ch[i][1]] + 1;
  sizb[i] = sizb[ch[i][0]] + sizb[ch[i][1]] + w[i];
  sum[i] = sum[ch[i][0]] + sum[ch[i][1]] +
           sizb[ch[i][1]] * (siz[ch[i][0]] + 1) + 1ll * w[i] * siz[ch[i][0]];
}
void rotate(int x) {
  int y = fa[x];
  bool d = (ch[y][0] == x);
  ch[y][!d] = ch[x][d];
  if (ch[x][d] != 0) fa[ch[x][d]] = y;
  fa[x] = fa[y];
  if (fa[y] != 0) ch[fa[y]][ch[fa[y]][1] == y] = x;
  ch[x][d] = y;
  fa[y] = x;
  pushup(y);
  pushup(x);
}
void splay(int i, int x) {
  for (int y = fa[x]; y != 0; rotate(x), y = fa[x])
    if (fa[y] && (ch[fa[y]][0] == y) == (ch[y][0] == x)) rotate(y);
  root[i] = x;
}
void Insert(int pos, int i, int x) {
  if (w[i] < w[x]) {
    if (ch[i][0] == 0) {
      ch[i][0] = x;
      fa[x] = i;
      splay(pos, x);
      return;
    }
    Insert(pos, ch[i][0], x);
  } else {
    if (ch[i][1] == 0) {
      ch[i][1] = x;
      fa[x] = i;
      splay(pos, x);
      return;
    }
    Insert(pos, ch[i][1], x);
  }
}
void copy(int i, int b) {
  if (i == 0) return;
  int lc = ch[i][0], rc = ch[i][1];
  copy(lc, b);
  ch[i][0] = ch[i][1] = fa[i] = 0;
  Insert(b, root[b], i);
  copy(rc, b);
}
int Find(int x) {
  if (f[x] == 0) return x;
  return f[x] = Find(f[x]);
}
void uniot(int x, int y) {
  int a = Find(x), b = Find(y);
  if (a != b) {
    if (s[a] > s[b]) swap(a, b);
    ans -= sum[root[a]] + sb[a] * l[a];
    ans -= sum[root[b]] + sb[b] * l[b];
    copy(root[a], b);
    ans += sum[root[b]];
    f[a] = b;
    s[b] += s[a];
    l[b] = min(l[b], l[a]);
    r[b] = max(r[b], r[a]);
    sb[b] += sb[a];
    ans += sb[b] * l[b];
  }
}
int main() {
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    scanf("%d %d", &a[i], &b[i]);
    ans -= 1ll * a[i] * b[i];
    int pos = a[i];
    if (l[Find(a[i])] != 0) pos = r[Find(a[i])] + 1;
    w[++k] = b[i];
    l[pos] = r[pos] = pos;
    sb[pos] = b[i];
    s[pos] = 1;
    ans += 1ll * b[i] * pos;
    pushup(k);
    root[pos] = k;
    if (l[Find(pos - 1)] != 0) uniot(pos - 1, pos);
    if (l[Find(pos + 1)] != 0) uniot(pos + 1, pos);
    printf("%lld\n", ans);
  }
}
