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>
const int MAXN = 200010;
const int MAXP = MAXN * 20;
int ls[MAXP], rs[MAXP], tot;
struct info {
  int a;
  long long b;
} tree[MAXP];
void mdf(int& u, int l, int r, int tar) {
  if (!u) u = ++tot;
  ++tree[u].a, tree[u].b += tar;
  if (l == r) return;
  int mid = l + r >> 1;
  if (tar <= mid)
    mdf(ls[u], l, mid, tar);
  else
    mdf(rs[u], mid + 1, r, tar);
}
long long ans;
int merge(int x, int y) {
  if (!x || !y) return x | y;
  ans += tree[ls[x]].b * tree[rs[y]].a;
  ans += tree[ls[y]].b * tree[rs[x]].a;
  ls[x] = merge(ls[x], ls[y]);
  rs[x] = merge(rs[x], rs[y]);
  tree[x].a += tree[y].a;
  tree[x].b += tree[y].b;
  return x;
}
struct itv {
  int l, r, rt;
  bool operator<(itv b) const { return l == b.l ? rt < b.rt : l < b.l; }
};
std::set<itv> S;
void ins(itv A) {
  auto it = S.insert(A).first, t = it;
  itv B;
  B.l = -1;
  if (++t != S.end() && A.r + 1 >= t->l)
    B = *t;
  else if ((t = it) != S.begin() && (--t)->r + 1 >= A.l)
    B = A, A = *t;
  if (B.l == -1) return;
  S.erase(A), S.erase(B);
  ans -= tree[B.rt].b * (B.l - A.l);
  A.r += tree[B.rt].a;
  A.rt = merge(A.rt, B.rt);
  ins(A);
}
int main() {
  std::ios_base::sync_with_stdio(false), std::cin.tie(0);
  int Q, n;
  std::cin >> Q;
  n = Q;
  while (Q-- > 0) {
    int x, y;
    std::cin >> x >> y;
    int tr = 0;
    mdf(tr, 1, n, y);
    ins((itv){x, x, tr});
    std::cout << ans << '\n';
  }
  return 0;
}
