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;
const int N = 4e5 + 5;
int n, a[N], b[N], p[N];
int node[18 * N], lc[18 * N], rc[18 * N], sz[18 * N];
long long sum[18 * N], val[18 * N], res, sub[N];
bool vis[N];
int Find(int x) {
  if (x == p[x]) return x;
  return p[x] = Find(p[x]);
}
void push(int id) {
  sz[id] = sz[lc[id]] + sz[rc[id]];
  sum[id] = sum[lc[id]] + sum[rc[id]];
  val[id] = val[lc[id]] + val[rc[id]] + sum[lc[id]] * sz[rc[id]];
}
int cnt = 0;
void Insert(int& id, int l, int r, int pos, int v) {
  if (!id) id = ++cnt;
  if (l == r) {
    sz[id] = 1;
    sum[id] = v;
    val[id] = v;
    return;
  }
  int mid = (l + r) / 2;
  if (pos <= mid)
    Insert(lc[id], l, mid, pos, v);
  else
    Insert(rc[id], mid + 1, r, pos, v);
  push(id);
}
int NodeMerge(int u, int v) {
  if (!u || !v) return u + v;
  lc[u] = NodeMerge(lc[u], lc[v]);
  rc[u] = NodeMerge(rc[u], rc[v]);
  if (lc[u] || rc[u])
    push(u);
  else {
    val[u] += val[v] + sum[v] * sz[u];
    sz[u] += sz[v];
    sum[u] += sum[v];
  }
  return u;
}
long long get(int u) { return val[node[u]] + (u - 1) * sum[node[u]]; }
void Merge(int x, int y) {
  int u = Find(x);
  int v = Find(y);
  p[v] = u;
  res -= get(u) + get(v);
  node[u] = NodeMerge(node[u], node[v]);
  res += get(u);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  for (int i = 1; i <= N - 5; i++) p[i] = i;
  for (int i = 1; i <= n; i++) {
    cin >> a[i] >> b[i];
    sub[i] = sub[i - 1] + 1ll * a[i] * b[i];
    int r = Find(a[i]);
    p[r] = r + 1;
    a[i] = r;
    Insert(node[a[i]], 1, N - 5, b[i], b[i]);
  }
  for (int i = 1; i <= N - 5; i++) p[i] = i;
  res = 0;
  for (int i = 1; i <= n; i++) {
    res += get(a[i]);
    if (vis[a[i] + 1]) Merge(a[i], a[i] + 1);
    if (vis[a[i] - 1]) Merge(a[i] - 1, a[i]);
    vis[a[i]] = true;
    cout << res - sub[i] << '\n';
  }
}
