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;
inline long long read() {
  register long long x = 0, f = 1;
  register char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
  return x * f;
}
void write(long long x) {
  if (x < 0) x = -x, putchar('-');
  if (x >= 10) write(x / 10);
  putchar(x % 10 + '0');
}
void writeln(long long x) {
  write(x);
  puts("");
}
const int maxn = 2e5 + 233;
const int mx = 4e5 + 10;
int nxt[mx + 5], fa[mx + 5];
int cnt[maxn * 20], lc[maxn * 20], rc[maxn * 20];
long long sum[maxn * 20];
int n;
inline int findf(int x) { return fa[x] == x ? x : fa[x] = findf(fa[x]); }
inline int findnxt(int x) { return nxt[x] == x ? x : nxt[x] = findnxt(nxt[x]); }
int tot = 0;
void insert(int &o, int l, int r, int x) {
  if (!o) o = ++tot;
  cnt[o]++;
  sum[o] += x;
  if (l == r) return;
  if (x <= ((l + r) >> 1))
    insert(lc[o], l, ((l + r) >> 1), x);
  else
    insert(rc[o], ((l + r) >> 1) + 1, r, x);
}
long long ans = 0;
void dfs(int o, int o2, int l, int r, long long sum, int cnt) {
  if (l == r) {
    ans += sum;
    ans -= 1ll * l * cnt;
  }
  if (lc[o2]) {
    sum += ::sum[lc[o2]];
    cnt += ::cnt[lc[o2]];
  }
  if (rc[o]) {
    dfs(rc[o], rc[o2], ((l + r) >> 1) + 1, r, sum, cnt);
  }
  if (lc[o2]) {
    sum -= ::sum[lc[o2]];
    cnt -= ::cnt[lc[o2]];
  }
  if (lc[o]) {
    dfs(lc[o], lc[o2], l, ((l + r) >> 1), sum, cnt);
  }
}
int Merge(int x, int y) {
  if (!x || !y) return x + y;
  lc[x] = Merge(lc[x], lc[y]);
  rc[x] = Merge(rc[x], rc[y]);
  sum[x] = sum[x] + sum[y];
  cnt[x] = cnt[x] + cnt[y];
  return x;
}
void merge(int &x, int &y) {
  if (cnt[x] < cnt[y]) {
    ans += cnt[y] * sum[x];
    ans -= cnt[x] * sum[y];
    swap(x, y);
  }
  dfs(y, x, 1, n, 0, 0);
  x = Merge(x, y);
}
int a[maxn], b[maxn], root[maxn * 2];
int main() {
  n = read();
  for (register int i = (1); i <= int(mx); ++i) nxt[i] = i, fa[i] = i;
  ans = 0;
  for (register int i = (1); i <= int(n); ++i) {
    a[i] = read(), b[i] = read();
    int tmp = a[i];
    a[i] = findnxt(a[i]);
    ans += 1ll * (a[i] - tmp) * b[i];
    nxt[a[i]] = a[i] + 1;
    insert(root[a[i]], 1, n, b[i]);
    if (root[findf(a[i] - 1)]) {
      merge(root[findf(a[i] - 1)], root[findf(a[i])]);
      fa[findf(a[i])] = findf(a[i] - 1);
    }
    if (root[findf(a[i] + 1)]) {
      merge(root[findf(a[i])], root[findf(a[i] + 1)]);
      fa[findf(a[i] + 1)] = findf(a[i]);
    }
    writeln(ans);
  }
  return 0;
}
