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>
const int maxn = 2e5;
long long n, a, b, c, ans;
class segTree {
  class node {
   public:
    node(int, int);
    void pushUp();
    friend class segTree;

   private:
    node* son[2];
    int l, r, siz;
    long long sum;
  };

 public:
  segTree();
  void insert(int);
  void merge(segTree);
  int siz();
  long long sum();

 private:
  void insert(node*, int);
  node* merge(node*, node*);
  node* root;
};
segTree::node::node(int l, int r) : l(l), r(r) {
  sum = siz = 0, son[0] = son[1] = nullptr;
}
void segTree::node::pushUp() {
  sum = siz = 0;
  if (son[0]) sum += son[0]->sum, siz += son[0]->siz;
  if (son[1]) sum += son[1]->sum, siz += son[1]->siz;
}
segTree::segTree() { root = new node(1, maxn); }
void segTree::insert(int x) { insert(root, x); }
void segTree::merge(segTree x) { root = merge(root, x.root); }
int segTree::siz() { return root->siz; }
long long segTree::sum() { return root->sum; }
void segTree::insert(node* nd, int x) {
  if (nd->l == nd->r)
    nd->siz = 1, nd->sum = x;
  else {
    int m = (nd->l + nd->r) >> 1;
    if (!nd->son[x > m])
      nd->son[x > m] =
          (x <= m) ? (new node(nd->l, m)) : (new node(m + 1, nd->r));
    insert(nd->son[x > m], x), nd->pushUp();
  }
}
segTree::node* segTree::merge(node* x, node* y) {
  if (!x || !y) return x ? x : y ? y : nullptr;
  if (x->son[0] && x->son[1]) ans -= x->son[0]->sum * x->son[1]->siz;
  if (y->son[0] && y->son[1]) ans -= y->son[0]->sum * y->son[1]->siz;
  x->son[0] = merge(x->son[0], y->son[0]),
  x->son[1] = merge(x->son[1], y->son[1]);
  if (x->son[0] && x->son[1]) ans += x->son[0]->sum * x->son[1]->siz;
  x->sum += y->sum, x->siz += y->siz;
  return x;
}
segTree seg[maxn << 1 | 1];
class DSU {
 public:
  DSU();
  int find(int);
  void merge(int, int);
  int right(int);

 private:
  int fa[maxn << 1 | 1], pos[maxn << 1 | 1];
};
DSU::DSU() {
  for (int i = 1; i <= maxn << 1; i++) fa[i] = pos[i] = i;
}
int DSU::find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void DSU::merge(int x, int y) {
  x = find(x), y = find(y), ans -= seg[x].sum() * x + seg[y].sum() * y,
  seg[x].merge(seg[y]), ans += seg[x].sum() * x, fa[y] = x, pos[x] = pos[y];
}
int DSU::right(int x) { return pos[find(x)]; }
DSU dsu;
int main() {
  std::cin.tie(0), std::cout.tie(0), std::ios::sync_with_stdio(false),
      std::cin >> n;
  for (int i = 1; i <= n; i++) {
    std::cin >> a >> b, c = seg[a].siz() ? dsu.right(a) + 1 : a,
                        ans += (c - a) * b, seg[c].insert(b);
    if (seg[c - 1].siz()) dsu.merge(c - 1, c);
    if (seg[c + 1].siz()) dsu.merge(c, c + 1);
    std::cout << ans << std::endl;
  }
  return 0;
}
