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 = 400005;
template <typename T>
inline void read(T &AKNOI) {
  T x = 0, flag = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  AKNOI = flag * x;
}
int f[MAXN], R[MAXN];
int tot, root[MAXN], lc[MAXN * 20], rc[MAXN * 20], cnt[MAXN * 20];
long long sum[MAXN * 20], ans;
int getf(int v) { return (f[v] == v) ? v : f[v] = getf(f[v]); }
void Insert(int &rt, int b, int e, int p) {
  rt = ++tot;
  cnt[rt] += 1;
  sum[rt] += p;
  if (b == e) return;
  int mid = (b + e) >> 1;
  if (p <= mid)
    Insert(lc[rt], b, mid, p);
  else
    Insert(rc[rt], mid + 1, e, p);
}
int Merge(int x, int y) {
  if (!x || !y) return x + y;
  ans -= sum[lc[x]] * cnt[rc[x]] + sum[lc[y]] * cnt[rc[y]];
  cnt[x] += cnt[y];
  sum[x] += sum[y];
  lc[x] = Merge(lc[x], lc[y]);
  rc[x] = Merge(rc[x], rc[y]);
  ans += sum[lc[x]] * cnt[rc[x]];
  return x;
}
void Combine(int x, int y) {
  x = getf(x);
  y = getf(y);
  f[y] = x;
  R[x] = R[y];
  ans -= sum[root[x]] * x + sum[root[y]] * y;
  root[x] = Merge(root[x], root[y]);
  ans += sum[root[x]] * x;
}
void solve() {
  for (int i = 1; i < MAXN; ++i) {
    f[i] = R[i] = i;
  }
  int n;
  read(n);
  for (int i = 1; i <= n; ++i) {
    int a, b;
    read(a);
    read(b);
    int p = root[a] ? R[getf(a)] + 1 : a;
    ans += 1LL * (p - a) * b;
    Insert(root[p], 1, n, b);
    if (root[p - 1]) Combine(p - 1, p);
    if (root[p + 1]) Combine(p, p + 1);
    printf("%lld\n", ans);
  }
}
int main() {
  solve();
  return 0;
}
