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 mxN = 2e5, mxSTS = 19 * mxN + 1;
int n, ai, bi;
long long ans;
map<int, int> mp;
struct segtree {
  int sts = 1, lc[mxSTS], rc[mxSTS], c1[mxSTS];
  long long c2[mxSTS];
  void bld(int &i, int l2 = 0, int r2 = n - 1) {
    i = sts++;
    c1[i] = 1;
    c2[i] = bi + 1;
    if (l2 == r2) return;
    int m2 = (l2 + r2) / 2;
    if (bi <= m2)
      bld(lc[i], l2, m2);
    else
      bld(rc[i], m2 + 1, r2);
  }
  void mrg(int &i1, int i2, int l2 = 0, int r2 = n - 1, int d1 = 0,
           int d2 = 0) {
    if (!i1) {
      swap(i1, i2);
      swap(d1, d2);
    }
    if (!i2) {
      ans += c2[i1] * d2;
      return;
    }
    int m2 = (l2 + r2) / 2;
    mrg(lc[i1], lc[i2], l2, m2, d1 + c1[rc[i1]], d2 + c1[rc[i2]]);
    mrg(rc[i1], rc[i2], m2 + 1, r2, d1, d2);
    c1[i1] = c1[lc[i1]] + c1[rc[i1]];
    c2[i1] = c2[lc[i1]] + c2[rc[i1]];
  }
} st;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  mp[-1] = 0;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> ai >> bi, --ai, --bi;
    auto it2 = --mp.upper_bound(ai), it1 = it2++;
    if (it1->first + st.c1[it1->second] < ai) it1 = mp.insert({ai, 0}).first;
    int c = 0;
    st.bld(c);
    ans -= (ai - it1->first) * st.c2[c];
    st.mrg(it1->second, c);
    if (it2 != mp.end() && it1->first + st.c1[it1->second] >= it2->first) {
      ans -= (it2->first - it1->first) * st.c2[it2->second];
      st.mrg(it1->second, it2->second);
      mp.erase(it2);
    }
    cout << ans << "\n";
  }
}
