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>
struct Segment_Tree {
  long long val, size, lson, rson;
} tree[5000100];
long long idx, ans, fa[1000100], R[1000100], root[1000100];
long long n, A, B;
void insert(long long &t, long long l, long long r, long long pos) {
  if (!t) t = ++idx;
  if (l == r) {
    tree[t].size = 1;
    tree[t].val = pos;
    return;
  }
  long long mid = (l + r) / 2;
  if (pos <= mid)
    insert(tree[t].lson, l, mid, pos);
  else
    insert(tree[t].rson, mid + 1, r, pos);
  tree[t].val = tree[tree[t].lson].val + tree[tree[t].rson].val;
  tree[t].size = tree[tree[t].lson].size + tree[tree[t].rson].size;
}
long long find(long long x) {
  if (fa[x] == x) return x;
  return fa[x] = find(fa[x]);
}
long long merge(long long x, long long y) {
  if (!x || !y) return x | y;
  ans -= tree[tree[x].lson].val * tree[tree[x].rson].size +
         tree[tree[y].lson].val * tree[tree[y].rson].size;
  tree[x].lson = merge(tree[x].lson, tree[y].lson);
  tree[x].rson = merge(tree[x].rson, tree[y].rson);
  ans += tree[tree[x].lson].val * tree[tree[x].rson].size;
  tree[x].size += tree[y].size;
  tree[x].val += tree[y].val;
  return x;
}
void solve(long long x, long long y) {
  long long fx = find(x), fy = find(y);
  fa[fy] = fx;
  ans -= tree[root[fx]].val * fx + tree[root[fy]].val * fy;
  root[fx] = merge(root[fx], root[fy]);
  ans += tree[root[fx]].val * fx;
  R[fx] = R[fy];
}
signed main() {
  scanf("%lld", &n);
  for (long long i = 1; i <= 400000; i++) fa[i] = R[i] = i;
  for (long long i = 1; i <= n; i++) {
    scanf("%lld%lld", &A, &B);
    long long p = root[A] ? R[find(A)] + 1 : A;
    ans -= A * B;
    insert(root[p], 1, n, B);
    ans += p * B;
    if (root[p - 1]) solve(p - 1, p);
    if (root[p + 1]) solve(p, p + 1);
    printf("%lld\n", ans);
  }
}
