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;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vpii = vector<pii>;
template <class T>
inline bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
inline bool ckmax(T& a, const T& b) {
  return b > a ? a = b, 1 : 0;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const char nl = '\n';
const int mxN = 2e5 + 10;
const int mxS = mxN * 19;
const int MOD = 1e9 + 7;
const ll infLL = 1e18;
const ld eps = 1e-6;
int n;
int rt[mxN], ch[mxS][2], alc = 1;
ll sum[mxS], cnt[mxS], ans;
ll sum1, sum2;
int bld(int a, int l = 1, int r = n) {
  int v = alc++;
  cnt[v] = 1, sum[v] = a;
  if (l == r) return v;
  int m = (l + r) / 2;
  if (a <= m)
    ch[v][0] = bld(a, l, m);
  else
    ch[v][1] = bld(a, m + 1, r);
  return v;
}
int merge(int a, int b) {
  if (!a && !b)
    return 0;
  else if (!b) {
    ans += sum2 * sum[a];
    sum1 += cnt[a];
    return a;
  } else if (!a) {
    ans += sum1 * sum[b];
    sum2 += cnt[b];
    return b;
  }
  ch[a][1] = merge(ch[a][1], ch[b][1]);
  ch[a][0] = merge(ch[a][0], ch[b][0]);
  sum[a] = sum[ch[a][0]] + sum[ch[a][1]];
  cnt[a] = cnt[ch[a][0]] + cnt[ch[a][1]];
  return a;
}
map<int, int> mp;
int32_t main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  mp[-1] = 0;
  for (int i = (0); i < (n); i++) {
    int a, b;
    cin >> a >> b;
    a--;
    auto it2 = mp.upper_bound(a), it1 = prev(it2);
    if (it1->first + cnt[it1->second] < a) {
      it1 = mp.insert({a, 0}).first;
    }
    rt[b] = bld(b);
    ans -= (a - it1->first) * sum[rt[b]];
    sum1 = 0, sum2 = 0;
    it1->second = merge(it1->second, rt[b]);
    if (it2 != mp.end() && it1->first + cnt[it1->second] >= it2->first) {
      ans -= (it2->first - it1->first) * sum[it2->second];
      sum1 = 0, sum2 = 0;
      it1->second = merge(it1->second, it2->second);
      mp.erase(it2);
    }
    cout << ans << nl;
  }
}
