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 N = 4e5 + 10;
int r[N], f[N], n, root[N], cnt = 0;
int siz[N * 20], son[N * 20][2];
long long ans = 0, sum[N * 20];
int getf(int x) { return (x == f[x]) ? x : f[x] = getf(f[x]); }
void update(int k) {
  siz[k] = siz[son[k][0]] + siz[son[k][1]];
  sum[k] = sum[son[k][0]] + sum[son[k][1]];
}
void insert(int &k, int l, int r, int x) {
  if (!k) k = ++cnt;
  if (l == r) {
    siz[k] = 1, sum[k] = x;
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid)
    insert(son[k][0], l, mid, x);
  else
    insert(son[k][1], mid + 1, r, x);
  update(k);
}
int merget(int x, int y) {
  if (!x || !y) return x | y;
  ans -= sum[son[x][0]] * siz[son[x][1]];
  ans -= sum[son[y][0]] * siz[son[y][1]];
  son[x][0] = merget(son[x][0], son[y][0]);
  son[x][1] = merget(son[x][1], son[y][1]);
  ans += sum[son[x][0]] * siz[son[x][1]];
  update(x);
  return x;
}
void mergef(int x, int y) {
  x = getf(x), y = getf(y), f[y] = x;
  ans -= sum[root[x]] * x + sum[root[y]] * y;
  root[x] = merget(root[x], root[y]);
  ans += sum[root[x]] * x;
  r[x] = r[y];
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i < N; i++) r[i] = f[i] = i;
  for (int i = 1, a, b, p; i <= n; i++) {
    scanf("%d%d", &a, &b);
    if (root[a])
      p = r[getf(a)] + 1;
    else
      p = a;
    ans -= 1LL * a * b;
    insert(root[p], 1, n, b);
    ans += 1LL * p * b;
    if (root[p - 1]) mergef(p - 1, p);
    if (root[p + 1]) mergef(p, p + 1);
    printf("%lld\n", ans);
  }
  return 0;
}
