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 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
void printvec(vector<T>& vec) {
  for (long long i = 0; i < vec.size(); i++) {
    cout << vec[i] << " ";
  }
  cout << endl;
}
struct node {
  node* l;
  node* r;
  long long val, prior, siz, sum;
};
typedef node* pnode;
pnode createnode(long long value) {
  pnode newnode = (pnode)malloc(sizeof(node));
  newnode->l = newnode->r = NULL;
  newnode->val = value;
  newnode->prior = rng();
  newnode->siz = 1;
  newnode->sum = value;
  return newnode;
}
long long getsiz(pnode t) {
  if (!t) return 0;
  return t->siz;
}
long long getsum(pnode t) {
  if (!t) return 0;
  return t->sum;
}
void upd_siz(pnode t) {
  if (!t) return;
  t->sum = t->val + getsum(t->l) + getsum(t->r);
  t->siz = getsiz(t->l) + 1;
  t->siz += getsiz(t->r);
}
void merge(pnode& t, pnode l, pnode r) {
  if (!l) {
    t = r;
    return;
  }
  if (!r) {
    t = l;
    return;
  }
  if (l->prior < r->prior) {
    t = r;
    merge(t->l, l, r->l);
  } else {
    t = l;
    merge(t->r, l->r, r);
  }
  upd_siz(t);
}
pnode haha[412345];
long long a[412345], b[412345];
void split(pnode t, pnode& l, pnode& r, long long x) {
  if (!t) {
    l = r = NULL;
    return;
  }
  if (t->val <= x) {
    l = t;
    split(t->r, l->r, r, x);
  } else {
    r = t;
    split(t->l, l, r->l, x);
  }
  upd_siz(t);
}
long long fre[412345];
long long findright(long long pos) {
  if (fre[pos] == pos) return pos;
  fre[pos] = findright(fre[pos]);
  return fre[pos];
}
long long dsu[412345];
long long par(long long u) {
  if (dsu[u] < 0) return u;
  dsu[u] = par(dsu[u]);
  return dsu[u];
}
long long st[412345];
long long ans = 0;
long long baba[412345];
vector<vector<long long> > vec(412345);
long long merge(long long u, long long v) {
  long long wow;
  u = par(u);
  v = par(v);
  if (dsu[u] < dsu[v]) {
    swap(u, v);
  }
  ans -= baba[u];
  ans -= baba[v];
  if (st[v] > st[u]) {
    baba[v] += dsu[u] * (haha[v]->sum);
    st[v] = st[u];
  }
  long long i;
  pnode l, r;
  for (i = 0; i < vec[u].size(); i++) {
    vec[v].push_back(vec[u][i]);
    split(haha[v], l, r, vec[u][i]);
    if (l) baba[v] += l->sum;
    if (!r) {
      wow = 0;
    } else {
      wow = r->siz;
    }
    baba[v] += (st[v] + wow) * vec[u][i];
    pnode foo = createnode(vec[u][i]);
    merge(haha[v], l, foo);
    merge(haha[v], haha[v], r);
  }
  vec[u].clear();
  dsu[v] += dsu[u];
  dsu[u] = v;
  ans += baba[v];
  return 0;
}
signed main() {
  std::ios::sync_with_stdio(false);
  long long n;
  cin >> n;
  long long i;
  for (i = 0; i < 412345; i++) {
    dsu[i] = -1;
    fre[i] = i;
    st[i] = i;
  }
  for (i = 0; i < n; i++) {
    cin >> a[i] >> b[i];
  }
  long long val;
  for (i = 0; i < n; i++) {
    ans -= a[i] * b[i];
    val = findright(a[i]);
    haha[val] = createnode(b[i]);
    fre[val] = val + 1;
    baba[val] = b[i] * val;
    vec[val].push_back(b[i]);
    ans += baba[val];
    if (fre[val - 1] != val - 1) {
      merge(val, val - 1);
    }
    if (fre[val + 1] != val + 1) {
      merge(val, val + 1);
    }
    cout << ans << endl;
  }
  return 0;
}
