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 n, a[400002], b[400002], f[400002], lx[400002], rx[400002], ls[400002 * 20],
    rs[400002 * 20], js, ct[400002 * 20], rt[400002];
bool vis[400002];
long long ans, he[400002 * 20], su[400002 * 20];
int getroot(int x) { return !f[x] ? x : f[x] = getroot(f[x]); }
void chng(int &o, int l, int r, int x) {
  if (!o) o = ++js;
  ct[o]++;
  su[o] += x;
  if (l == r) {
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid)
    chng(ls[o], l, mid, x);
  else
    chng(rs[o], mid + 1, r, x);
  he[o] = he[ls[o]] + he[rs[o]] + su[ls[o]] * ct[rs[o]];
}
void merge(int &o, int u, int v, int l, int r) {
  if ((!u) || (!v)) {
    o = u | v;
    return;
  }
  int mid = (l + r) >> 1;
  ct[o] = ct[u] + ct[v], su[o] = su[u] + su[v];
  merge(ls[o], ls[u], ls[v], l, mid);
  merge(rs[o], rs[u], rs[v], mid + 1, r);
  he[o] = he[ls[o]] + he[rs[o]] + su[ls[o]] * ct[rs[o]];
}
inline void un(int x, int y) {
  if (x == y) return;
  ans -= he[rt[x]] + su[rt[x]] * lx[x];
  ans -= he[rt[y]] + su[rt[y]] * lx[y];
  f[x] = y;
  lx[y] = min(lx[y], lx[x]), rx[y] = max(rx[y], rx[x]);
  merge(rt[y], rt[x], rt[y], 1, 2 * n);
  ans += he[rt[y]] + su[rt[y]] * lx[y];
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &a[i], &b[i]);
    int x = getroot(a[i]);
    ans -= 1ll * a[i] * b[i];
    if (!vis[x]) {
      lx[x] = rx[x] = x;
      chng(rt[x], 1, 2 * n, b[i]);
      vis[x] = 1;
      ans += su[rt[x]] * lx[x];
      if (vis[x - 1]) un(getroot(x - 1), x);
      if (vis[x + 1]) un(getroot(x + 1), x);
    } else {
      int nx = rx[x] + 1;
      lx[nx] = rx[nx] = nx;
      vis[nx] = 1;
      chng(rt[nx], 1, 2 * n, b[i]);
      ans += su[rt[nx]] * lx[nx];
      if (vis[nx - 1]) un(getroot(nx - 1), nx);
      if (vis[nx + 1]) un(getroot(nx + 1), nx);
    }
    printf("%lld\n", ans);
  }
}
