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 = 414514;
int n, tt;
int f[N], r[N];
int rt[N], ls[N * 30], rs[N * 30], sz[N * 30];
long long su[N * 30], as;
void add(int &i, int l, int r, int s) {
  if (!i) i = ++tt;
  if (l == r) {
    sz[i] = 1, su[i] = s;
    return;
  }
  if (s <= ((l + r) >> 1))
    add(ls[i], l, ((l + r) >> 1), s);
  else
    add(rs[i], ((l + r) >> 1) + 1, r, s);
  sz[i] = sz[ls[i]] + sz[rs[i]];
  su[i] = su[ls[i]] + su[rs[i]];
}
void merge(int &x, int y) {
  if (!x || !y) {
    x = x | y;
    return;
  }
  as -= 1ll * su[ls[x]] * sz[rs[x]] + 1ll * su[ls[y]] * sz[rs[y]];
  merge(ls[x], ls[y]);
  merge(rs[x], rs[y]);
  as += 1ll * su[ls[x]] * sz[rs[x]];
  sz[x] += sz[y];
  su[x] += su[y];
  return;
}
int get(int x) { return x == f[x] ? x : f[x] = get(f[x]); }
void mrg(int x, int y) {
  x = get(x), y = get(y);
  f[y] = x;
  as -= 1ll * su[rt[x]] * x + 1ll * su[rt[y]] * y;
  merge(rt[x], rt[y]);
  as += 1ll * su[rt[x]] * x;
  r[x] = r[y];
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= 4e5; i++) f[i] = r[i] = i;
  for (int i = 1, x, y; i <= n; i++) {
    scanf("%d%d", &x, &y);
    int k = rt[x] ? r[get(x)] + 1 : x;
    as -= 1ll * x * y;
    as += 1ll * k * y;
    add(rt[k], 1, n, y);
    if (rt[k - 1]) mrg(k - 1, k);
    if (rt[k + 1]) mrg(k, k + 1);
    printf("%lld\n", as);
  }
}
