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;
int const N = 200000;
long long an;
struct ND {
  ND *l, *r;
  int a, sz;
  long long sm;
  ND(int a0, int sz0 = 0, long long sm0 = 0)
      : l(0), r(0), a(a0), sz(sz0), sm(sm0) {}
};
int sz(ND *nd) { return nd ? nd->sz : 0; }
long long sm(ND *nd) { return nd ? nd->sm : 0; }
struct T {
  ND *R;
  T() : R(0) {}
  ND *bld(int a, int b, int l, int r) {
    if (l == r) return new ND(a, 1, b);
    ND *nd = new ND(a, 1, b);
    int m = l + r >> 1;
    if (b <= m)
      nd->l = bld(a, b, l, m);
    else
      nd->r = bld(a, b, m + 1, r);
    return nd;
  }
  void sl(ND *nd) {
    int a = nd->a;
    if (nd->r) nd->r->a = a, a += nd->r->sz;
    if (nd->l) nd->l->a = a;
  }
  void bld(int a, int b) { R = bld(a, b, 1, N); }
  void join(ND *&x, ND *&y, int &a) {
    if (!x && !y) return;
    if (!x) swap(x, y);
    if (!y) {
      an += (a - x->a) * x->sm, x->a = a, a += x->sz;
      return;
    }
    sl(x);
    sl(y);
    x->a = a;
    join(x->r, y->r, a);
    join(x->l, y->l, a);
    delete y;
    x->sz = sz(x->l) + sz(x->r);
    x->sm = sm(x->l) + sm(x->r);
  }
  void operator+=(T &o) {
    int a = min(R->a, o.R->a);
    join(R, o.R, a);
  }
} sg[N];
struct S {
  int l, r, i;
  S(int a, int b = 0, int c = 0) : l(a), r(b), i(c) {}
  bool operator<(S const &o) const { return r < o.r; }
};
int main() {
  int n;
  scanf("%d", &n);
  set<S> st;
  st.insert(S(1e9, 1e9));
  for (int i = 0; i < (int)(n); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    sg[i].bld(a, b);
    set<S>::iterator it = st.lower_bound(S(0, a));
    if (it->l <= a + 1) {
      S t = *it;
      if (a + 1 == t.l)
        t.l = a, sg[i] += sg[t.i];
      else
        ++t.r, sg[i] += sg[t.i];
      st.erase(it++);
      if (it->l == t.r) {
        sg[i] += sg[it->i];
        t.r = it->r;
        st.erase(it);
      }
      t.i = i;
      st.insert(t);
    } else
      st.insert(S(a, a + 1, i));
    printf("%lld\n", an);
  }
}
