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;
using ll = long long;
int n;
class segment_tree {
 public:
  using pointer = segment_tree*;
  int l, r, m;
  ll sz, value, sum;
  pointer left, right;
  segment_tree(int l, int r, int u) {
    this->l = l;
    this->r = r;
    m = (l + r) / 2;
    value = 0;
    sz = 1;
    sum = u;
    left = right = nullptr;
    if (l == r) return;
    if (m >= u)
      left = new segment_tree(l, m, u);
    else
      right = new segment_tree(m + 1, r, u);
  }
  void up() {
    if (left == nullptr) {
      if (right == nullptr) {
      } else {
        sz = right->sz;
        value = right->value;
        sum = right->sum;
      }
    } else {
      if (right == nullptr) {
        sz = left->sz;
        value = left->value;
        sum = left->sum;
      } else {
        value = left->value + right->value + left->sum * right->sz;
        sz = left->sz + right->sz;
        sum = left->sum + right->sum;
      }
    }
  }
  friend pointer merge(pointer u, pointer v) {
    if (u == nullptr) return v;
    if (v == nullptr) return u;
    u->left = merge(u->left, v->left);
    u->right = merge(u->right, v->right);
    u->up();
    return u;
  }
};
segment_tree::pointer tree[200002];
int r[200002];
int first[200002];
ll ans = 0;
int root(int u) {
  if (r[u] < 0) return u;
  return r[u] = root(r[u]);
}
ll cost(int u) {
  u = root(u);
  if (tree[u] == nullptr) return 0;
  return tree[u]->value + tree[u]->sum * first[u];
}
void unite(int u, int v) {
  if (u < 1 || u > 200000) return;
  if (v < 1 || v > 200000) return;
  u = root(u);
  v = root(v);
  if (u == v) return;
  if (r[u] > r[v]) swap(u, v);
  ans -= cost(u);
  ans -= cost(v);
  r[u] += r[v];
  r[v] = u;
  first[u] = min(first[u], first[v]);
  tree[u] = merge(tree[u], tree[v]);
  ans += cost(u);
  unite(root(u), first[root(u)] + tree[root(u)]->sz);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  for (int i = 0; i <= 200001; i++) r[i] = -1;
  for (int i = 0; i <= 200001; i++) first[i] = i;
  for (int i = 1, a, b; i <= n; i++) {
    cin >> a >> b;
    auto temp = new segment_tree(1, n, b);
    ans -= ((ll)(a)) * b;
    a = root(a);
    ans -= cost(a);
    tree[a] = merge(tree[a], temp);
    ans += cost(a);
    unite(root(a), first[root(a)] + tree[root(a)]->sz);
    cout << ans << '\n';
  }
}
