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 = 2e5 + 5, M = N * 20;
int n, sz, A, B, ls[M], rs[M];
long long c0[M], c1[M], c2[M];
void pu(int o) {
  c0[o] = c0[ls[o]] + c0[rs[o]];
  c1[o] = c1[ls[o]] + c1[rs[o]];
  c2[o] = c2[ls[o]] + c2[rs[o]] + c1[ls[o]] * c0[rs[o]];
}
int node(int p, int l, int r) {
  int o = ++sz;
  c0[o]++, c1[o] += p;
  if (p > ((l + r) / 2))
    rs[o] = node(p, ((l + r) / 2) + 1, r);
  else if (l < r)
    ls[o] = node(p, l, ((l + r) / 2));
  return o;
}
void join(int& o, int oo) {
  if (!o || !oo) {
    o += oo;
    return;
  }
  join(ls[o], ls[oo]), join(rs[o], rs[oo]), pu(o);
}
set<pair<int, int>, greater<pair<int, int>>> s;
int main() {
  cin >> n;
  long long as = 0;
  for (int i = (1); i <= (n); i++) {
    scanf("%d%d", &A, &B);
    auto it = s.lower_bound({A, 1e9});
    s.insert({A, node(B, 1, 200000)});
    if (it == s.end() || A > it->first + c0[it->second]) it--;
    auto [l, t] = *it;
    while (it != s.begin()) {
      auto [L, T] = *--it;
      it++;
      if (L <= l + c0[t])
        as -= c1[T] * (L - l) + c2[t] + c2[T], join(t, T), as += c2[t],
            s.erase({L, T});
      else
        break;
    }
    printf("%lld\n", as);
  }
  return 0;
}
