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 char gc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline long long read() {
  long long x = 0;
  char ch = getchar();
  bool positive = 1;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') positive = 0;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return positive ? x : -x;
}
inline void write(long long a) {
  if (a < 0) {
    a = -a;
    putchar('-');
  }
  if (a >= 10) write(a / 10);
  putchar('0' + a % 10);
}
inline void wri(long long a) {
  write(a);
  putchar(' ');
}
inline void writeln(long long a) {
  write(a);
  puts("");
}
const int N = 400005, M = 10000000;
long long dq, sum[M], tree[M], ycl[N];
int sz[M], lson[M], rson[M];
int vis[N], a[N], b[N], father[N], rt[N], nodecnt;
inline void push_up(int nod) {
  sum[nod] = sum[lson[nod]] + sum[rson[nod]];
  sz[nod] = sz[lson[nod]] + sz[rson[nod]];
  tree[nod] =
      tree[lson[nod]] + tree[rson[nod]] + sz[rson[nod]] * sum[lson[nod]];
}
void insert(int l, int r, int pos, int de, int &nod) {
  if (!nod) nod = ++nodecnt;
  if (l == r) {
    tree[nod] = sum[nod] = de;
    sz[nod] = 1;
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid)
    insert(l, mid, pos, de, lson[nod]);
  else
    insert(mid + 1, r, pos, de, rson[nod]);
  push_up(nod);
}
inline int merge(int a, int b) {
  if (!a || !b) return a | b;
  lson[a] = merge(lson[a], lson[b]);
  rson[a] = merge(rson[a], rson[b]);
  if (!lson[a] && !rson[a]) {
    tree[a] += tree[b] + sum[b] * sz[a];
    sum[a] += sum[b];
    sz[a] += sz[b];
  } else
    push_up(a);
  return a;
}
long long get(int nod) { return tree[rt[nod]] + (nod - 1) * sum[rt[nod]]; }
inline int getfather(int x) {
  return father[x] == x ? x : father[x] = getfather(father[x]);
}
void Merge(int a, int b) {
  int x = getfather(a), y = getfather(b);
  father[y] = x;
  dq -= get(x);
  dq -= get(y);
  rt[x] = merge(rt[x], rt[y]);
  dq += get(x);
}
int n;
int main() {
  n = read();
  for (int i = 1; i < N; i++) father[i] = i;
  for (int i = 1; i <= n; i++) {
    a[i] = read();
    b[i] = read();
    ycl[i] = ycl[i - 1] + (long long)a[i] * b[i];
    a[i] = getfather(a[i]);
    father[a[i]] = a[i] + 1;
    insert(1, N - 1, b[i], b[i], rt[a[i]]);
  }
  for (int i = 1; i < N; i++) father[i] = i;
  for (int i = 1; i <= n; i++) {
    dq += 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]] = 1;
    writeln(dq - ycl[i]);
  }
}
