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 maxn = 4e5 + 5;
const int maxm = maxn * 20;
long long st[maxm], siz[maxm], sum[maxm];
int n;
int fa[maxn], maxr[maxn], minl[maxn], A[maxn], B[maxn];
int now;
int L[maxm], R[maxm], RT[maxn];
long long ans;
void build(int &x, int l, int r, int px) {
  if (!x) x = ++now;
  if (l == r) {
    siz[x] = 1, sum[x] = px;
    return;
  }
  int mid = (l + r) >> 1;
  if (px <= mid)
    build(L[x], l, mid, px);
  else
    build(R[x], mid + 1, r, px);
  siz[x] = siz[L[x]] + siz[R[x]], sum[x] = sum[L[x]] + sum[R[x]];
}
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int &x, int y, int l, int r) {
  if (!x || !y) {
    x = x + y;
    return;
  }
  if (l == r) {
    st[x] = st[x] + st[y] + sum[x] * siz[y];
    siz[x] += siz[y], sum[x] += sum[y];
    return;
  }
  int mid = (l + r) >> 1;
  merge(L[x], L[y], l, mid);
  merge(R[x], R[y], mid + 1, r);
  st[x] = st[L[x]] + st[R[x]] + sum[L[x]] * siz[R[x]];
  siz[x] = siz[L[x]] + siz[R[x]], sum[x] = sum[L[x]] + sum[R[x]];
}
void solve(int x, int y) {
  int u = RT[x], v = RT[y];
  ans -= sum[u] * minl[x] + sum[v] * minl[y] + st[u] + st[v];
  merge(RT[x], RT[y], 1, n);
  u = RT[x];
  ans += st[u] + sum[u] * minl[x];
  fa[y] = x, maxr[x] = maxr[y];
}
void update(int x, int y) {
  int p = find(x - 1), q = find(x + 1), u = find(x);
  build(RT[u], 1, n, y);
  if (RT[p]) u = find(x), solve(p, u);
  if (RT[q]) u = find(x), solve(u, q);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= 4e5; ++i) fa[i] = i, minl[i] = i, maxr[i] = i;
  for (int i = 1; i <= n; ++i) scanf("%d%d", &A[i], &B[i]);
  for (int i = 1; i <= n; ++i) {
    int u = find(A[i]);
    int pos = RT[u] ? maxr[u] + 1 : u;
    ans += (long long)(pos - A[i]) * B[i];
    update(pos, B[i]);
    printf("%lld\n", ans);
  }
  return 0;
}
