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 int read() {
  int x = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return x * f;
}
const int N = 400005;
int ls[N * 20], rs[N * 20], siz[N * 20], Root[N], R[N], fa[N], Index;
long long sum[N * 20], Ans;
void Insert(int l, int r, int &now, int p) {
  if (!now) now = ++Index;
  if (l == r) {
    siz[now] = 1, sum[now] = p;
    return;
  }
  int mid = (l + r) >> 1;
  if (p <= mid)
    Insert(l, mid, ls[now], p);
  else
    Insert(mid + 1, r, rs[now], p);
  sum[now] = sum[ls[now]] + sum[rs[now]],
  siz[now] = siz[ls[now]] + siz[rs[now]];
}
int Merge(int x, int y) {
  if (!x || !y) return x | y;
  Ans -= sum[ls[x]] * siz[rs[x]] + sum[ls[y]] * siz[rs[y]];
  ls[x] = Merge(ls[x], ls[y]);
  rs[x] = Merge(rs[x], rs[y]);
  Ans += sum[ls[x]] * siz[rs[x]], siz[x] += siz[y], sum[x] += sum[y];
  return x;
}
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void solve(int x, int y) {
  x = find(x), y = find(y);
  fa[y] = x;
  Ans -= sum[Root[x]] * x + sum[Root[y]] * y;
  Root[x] = Merge(Root[x], Root[y]);
  Ans += sum[Root[x]] * x;
  R[x] = R[y];
}
int main() {
  int n = read();
  for (int i = 1; i <= 400000; ++i) fa[i] = i, R[i] = i;
  for (int i = 1; i <= n; ++i) {
    int a = read(), b = read();
    int p = Root[a] ? R[find(a)] + 1 : a;
    Ans -= 1ll * a * b;
    Insert(1, n, Root[p], b);
    Ans += 1ll * p * b;
    if (Root[p - 1]) solve(p - 1, p);
    if (Root[p + 1]) solve(p, p + 1);
    printf("%I64d\n", Ans);
  }
  return 0;
}
