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;
using vvi = vector<vector<int>>;
using vi = vector<int>;
using vvll = vector<vector<long long>>;
using vll = vector<long long>;
using vd = vector<double>;
using vvd = vector<vector<double>>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char* x) { cerr << '\"' << x << '\"'; }
void __print(const string& x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V>& x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T& x) {
  int f = 0;
  cerr << '{';
  for (auto& i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct Node {
  Node *l = 0, *r = 0;
  int val, y, c = 1;
  ll s;
  int pos;
  Node(int val, int pos) : val(val), y(rng()), s(val), pos(pos) {}
  void recalc();
};
int cnt(Node* n) { return n ? n->c : 0; }
ll sum(Node* n) { return n ? n->s : 0LL; }
void Node::recalc() {
  c = cnt(l) + cnt(r) + 1;
  s = sum(l) + sum(r) + val;
}
template <class F>
void each(Node* n, F f) {
  if (n) {
    each(n->l, f);
    f(n->val, n->pos);
    each(n->r, f);
  }
}
pair<Node*, Node*> split(Node* n, int k) {
  if (!n) return {};
  if (n->val <= k) {
    auto pa = split(n->l, k);
    n->l = pa.second;
    n->recalc();
    return {pa.first, n};
  } else {
    auto pa = split(n->r, k);
    n->r = pa.first;
    n->recalc();
    return {n, pa.second};
  }
}
Node* merge(Node* l, Node* r) {
  if (!l) return r;
  if (!r) return l;
  if (l->y > r->y) {
    l->r = merge(l->r, r);
    l->recalc();
    return l;
  } else {
    r->l = merge(l, r->l);
    r->recalc();
    return r;
  }
}
struct Tree {
  Node* root;
  int start;
  ll value;
  Tree(Node* _root, int _start, ll _value)
      : root(_root), start(_start), value(_value) {}
};
void __print(Tree t) {
  cerr << '{' << t.start << ',' << t.value << ',' << cnt(t.root) << '}';
}
bool operator<(Tree a, Tree b) { return a.start < b.start; }
Tree insert(Tree t, int a, int b) {
  auto sp = split(t.root, b);
  t.value += sum(sp.second);
  int new_pos = t.start + cnt(sp.first);
  t.value += (ll)b * (new_pos - a);
  ;
  Node* new_node = new Node(b, a);
  t.root = merge(merge(sp.first, new_node), sp.second);
  return t;
}
Tree merge_trees(Tree a, Tree b) {
  assert(a < b);
  assert(a.start + cnt(a.root) >= b.start);
  if (cnt(a.root) < cnt(b.root)) {
    ;
    b.value -= sum(b.root) * (b.start - a.start);
    b.start = a.start;
    swap(a, b);
  };
  each(b.root, [&](int val, int pos) {
    ;
    a = insert(a, pos, val);
  });
  return a;
}
void solve() {
  int n;
  cin >> n;
  set<Tree> trees;
  ll ans = 0;
  while (n--) {
    ;
    int a, b;
    cin >> a >> b;
    Tree tmp = Tree(new Node(b, a), a, 0);
    auto it = trees.upper_bound(tmp);
    if (it != trees.begin() && prev(it)->start <= a &&
        a <= prev(it)->start + cnt(prev(it)->root)) {
      ;
      it = prev(it);
      Tree t = insert(*it, a, b);
      ans -= it->value;
      trees.erase(it);
      ans += t.value;
      ;
      it = trees.insert(t).first;
    } else {
      ;
      ans += tmp.value;
      it = trees.insert(tmp).first;
    };
    auto nit = next(it);
    if (nit != trees.end() && it->start + cnt(it->root) >= nit->start) {
      ;
      Tree t = merge_trees(*it, *nit);
      ans -= it->value;
      ans -= nit->value;
      trees.erase(it);
      trees.erase(nit);
      ans += t.value;
      trees.insert(t);
    }
    cout << ans << endl;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve();
  return 0;
}
