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;
mt19937 rnd;
template <typename T>
struct Treap {
  struct Node {
    T val, sum;
    int pri, cnt;
    Node *lch, *rch;
    Node(T v) : val(v), pri(rnd()), cnt(1), sum(v) { lch = rch = nullptr; }
  };
  Node* node;
  Treap(Node* n = nullptr) { node = n; }
  Treap(T v) { node = new Node(v); }
  void initialize(T v) { node = new Node(v); }
  int count(Node* t) { return !t ? 0 : t->cnt; }
  T sum(Node* t) { return !t ? 0 : t->sum; }
  int count() { return count(node); }
  T sum() { return sum(node); }
  Node* update(Node* t) {
    t->cnt = count(t->lch) + count(t->rch) + 1;
    t->sum = sum(t->lch) + sum(t->rch) + t->val;
    return t;
  }
  Node* merge(Node* l, Node* r) {
    if (!l || !r) return !l ? r : l;
    if (l->val > r->val) swap(l, r);
    if (l->pri > r->pri) {
      l->rch = merge(l->rch, r);
      return update(l);
    } else {
      r->lch = merge(l, r->lch);
      return update(r);
    }
  }
  void merge(Treap* tr) { node = merge(tr->node); }
  pair<Node*, Node*> split(Node* t, T v) {
    if (!t) return make_pair(nullptr, nullptr);
    if (v < t->val) {
      auto s = split(t->lch, v);
      t->lch = s.second;
      return {s.first, update(t)};
    } else {
      auto s = split(t->rch, v);
      t->rch = s.first;
      return {update(t), s.second};
    }
  }
  pair<Treap*, Treap*> split(T v) {
    auto p = split(node, v);
    node = p.first;
    auto t2 = new Treap(p.second);
    return make_pair(this, t2);
  }
  void insert(T v) {
    auto s = split(node, v);
    auto n = new Node(v);
    node = merge(s.first, n);
    node = merge(node, s.second);
  }
  void erase(int v) {
    auto s1 = split(node, v - 1);
    auto s2 = split(s1.second, v);
    merge(s1.first, s2.second);
  }
  int getcount(Node* t, T v, bool larger) {
    if (!t) return 0;
    int ret = 0;
    if (larger) {
      if (v <= t->val) ret++;
      ret += v <= t->val ? count(t->rch) : getcount(t->rch, v, larger);
      ret += v <= t->val ? getcount(t->lch, v, larger) : 0;
    } else {
      if (v >= t->val) ret++;
      ret += v >= t->val ? count(t->lch) : getcount(t->lch, v, larger);
      ret += v >= t->val ? getcount(t->rch, v, larger) : 0;
    }
    return ret;
  }
  int getcount(T v, bool larger) { return getcount(node, v, larger); }
  T getsum(Node* t, T v, bool larger) {
    if (!t) return 0;
    T ret = 0;
    if (larger) {
      if (v <= t->val) ret += t->val;
      ret += v <= t->val ? sum(t->rch) : getsum(t->rch, v, larger);
      ret += v <= t->val ? getsum(t->lch, v, larger) : 0;
    } else {
      if (v >= t->val) ret += t->val;
      ret += v >= t->val ? sum(t->lch) : getsum(t->lch, v, larger);
      ret += v >= t->val ? getsum(t->rch, v, larger) : 0;
    }
    return ret;
  }
  T getsum(T v, bool larger) { return getsum(node, v, larger); }
  void dump(Node* t, vector<T>& ret) {
    if (!t) return;
    dump(t->lch, ret);
    ret.push_back(t->val);
    dump(t->rch, ret);
  }
  vector<T> dump() {
    vector<T> ret;
    dump(node, ret);
    return ret;
  }
};
int64_t ans = 0;
void merge(Treap<int64_t>* from, Treap<int64_t>* to, int fromlb, int tolb) {
  if (!from) return;
  vector<int64_t> values = from->dump();
  for (auto&& v : values) {
    ans += to->getsum(v, false);
    ans += v * (tolb - fromlb + to->getcount(v, true));
  }
  for (auto&& v : values) to->insert(v);
}
struct UnionFind {
  vector<int> par, sz, lb;
  vector<Treap<int64_t>*> tr;
  UnionFind(int n = 0) {
    if (n > 0) initialize(n);
  }
  void initialize(int n) {
    par.resize(n);
    sz.resize(n);
    lb.resize(n);
    tr.resize(n);
    for (int i = 0; i < n; i++) {
      par[i] = i;
      sz[i] = 1;
      lb[i] = i;
      tr[i] = nullptr;
    }
  }
  int find(int x) {
    if (par[x] == x) {
      return x;
    } else {
      return par[x] = find(par[x]);
    }
  }
  void add(int a, int64_t b) {
    int root = find(a);
    auto t = new Treap<int64_t>(b);
    if (tr[root]) {
      merge(t, tr[root], a, lb[root]);
      unite(root, lb[root] + sz[root], false);
    } else {
      tr[root] = t;
    }
    root = find(a);
    int neighbor = find(lb[root] + sz[root]);
    if (tr[neighbor]) unite(root, neighbor, true);
    root = find(a);
    neighbor = find(lb[root] - 1);
    if (tr[neighbor]) unite(neighbor, root, true);
  }
  void unite(int x, int y, bool tm) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    int nlb = lb[x];
    if (tm && sz[x] < sz[y]) swap(x, y);
    par[y] = x;
    sz[x] += sz[y];
    if (tm) {
      merge(tr[y], tr[x], lb[y], lb[x]);
      ans += (nlb - lb[x]) * (*tr[x]).sum();
    }
    lb[x] = nlb;
  }
  bool same(int x, int y) { return find(x) == find(y); }
};
int N;
const int MAX = 400010;
int64_t A[MAX], B[MAX];
UnionFind uf(MAX);
int main() {
  int i, j, k;
  cin >> N;
  for (i = 1; i <= N; i++) scanf("%lld %lld", &A[i], &B[i]);
  for (i = 1; i <= N; i++) {
    uf.add(A[i], B[i]);
    cout << ans << endl;
  }
  return 0;
}
