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;
template <typename T>
inline bool chkmin(T &a, T b) {
  return b < a ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T &a, T b) {
  return b > a ? a = b, 1 : 0;
}
inline int read() {
  int x(0), sgn(1);
  char ch(getchar());
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') sgn = -1;
  for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
  return x * sgn;
}
void File() {}
template <int Maxn>
struct Segment_Tree {
  int ls[Maxn], rs[Maxn], tot[Maxn], Size;
  Segment_Tree() { Size = 0; }
  long long res[Maxn], val[Maxn];
  inline void Push_Up(int o) {
    tot[o] = tot[ls[o]] + tot[rs[o]];
    val[o] = val[ls[o]] + val[rs[o]];
    res[o] = res[ls[o]] + res[rs[o]] + val[ls[o]] * tot[rs[o]];
  }
  void Update(int &o, int l, int r, int up) {
    if (!o) o = ++Size;
    if (l == r) {
      tot[o] = 1;
      val[o] = up;
      return;
    }
    int mid = (l + r) >> 1;
    if (up <= mid)
      Update(ls[o], l, mid, up);
    else
      Update(rs[o], mid + 1, r, up);
    Push_Up(o);
  }
  int Merge(int x, int y, int l, int r) {
    if (!x || !y) return x | y;
    int mid = (l + r) >> 1;
    ls[x] = Merge(ls[x], ls[y], l, mid);
    rs[x] = Merge(rs[x], rs[y], mid + 1, r);
    Push_Up(x);
    return x;
  }
};
const int N = 4e5 + 1e3;
Segment_Tree<N * 20> T;
int rt[N], fa[N], lb[N], rb[N], n;
long long ans = 0;
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void Merge(int x, int y) {
  x = find(x);
  y = find(y);
  fa[y] = x;
  ans -= T.res[rt[x]] + 1ll * lb[x] * T.val[rt[x]];
  ans -= T.res[rt[y]] + 1ll * lb[y] * T.val[rt[y]];
  chkmin(lb[x], lb[y]);
  chkmax(rb[x], rb[y]);
  rt[x] = T.Merge(rt[x], rt[y], 1, n);
  ans += T.res[rt[x]] + 1ll * lb[x] * T.val[rt[x]];
}
int main() {
  File();
  n = read();
  for (register int i = (1), iend = (int)(N - 1e3); i <= iend; ++i)
    lb[i] = rb[i] = fa[i] = i;
  for (register int i = (1), iend = (int)(n); i <= iend; ++i) {
    int a = read(), b = read(), t;
    ans -= 1ll * a * b;
    t = rt[find(a)] ? rb[find(a)] + 1 : a;
    T.Update(rt[t], 1, n, b);
    ans += T.res[rt[t]] + 1ll * t * T.val[rt[t]];
    if (rt[find(t - 1)]) Merge(t, t - 1);
    if (rt[find(t + 1)]) Merge(t + 1, t);
    printf("%lld\n", ans);
  }
  return 0;
}
