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;
template <typename A, typename B>
inline void chmin(A& a, B b) {
  if (a > b) a = b;
}
template <typename A, typename B>
inline void chmax(A& a, B b) {
  if (a < b) a = b;
}
template <class A, class B>
ostream& operator<<(ostream& ost, const pair<A, B>& p) {
  ost << "{" << p.first << "," << p.second << "}";
  return ost;
}
template <class T>
ostream& operator<<(ostream& ost, const vector<T>& v) {
  ost << "{";
  for (long long i = 0; i < v.size(); i++) {
    if (i) ost << ",";
    ost << v[i];
  }
  ost << "}";
  return ost;
}
struct MergingSegmentTree {
  static const long long LG = 18;
  static const long long SEG = 1 << LG;
  static const long long OP = SEG;
  static const long long SZ = OP * LG + 1;
  long long tail;
  vector<long long> chl, chr, sz, sum, opt;
  MergingSegmentTree() : tail(1), chl(SZ), chr(SZ), sz(SZ), sum(SZ), opt(SZ) {}
  long long build(long long val, long long l = 0, long long r = SEG) {
    long long k = tail++;
    sz[k] = 1;
    sum[k] = val;
    opt[k] = 0;
    if (l + 1 == r) return k;
    long long m = (l + r) >> 1;
    if (val < m)
      chl[k] = build(val, l, m);
    else
      chr[k] = build(val, m, r);
    return k;
  }
  long long merge(long long t1, long long t2, long long l = 0,
                  long long r = SEG) {
    if (t1 && t2)
      ;
    else
      return t1 ^ t2;
    sum[t1] += sum[t2];
    sz[t1] += sz[t2];
    if (l + 1 == r) {
      opt[t1] = sz[t1] * (sz[t1] - 1) / 2 * l;
      return t1;
    }
    long long m = (l + r) >> 1;
    chl[t1] = merge(chl[t1], chl[t2], l, m);
    chr[t1] = merge(chr[t1], chr[t2], m, r);
    opt[t1] = opt[chl[t1]] + sz[chr[t1]] * sum[chl[t1]] + opt[chr[t1]];
    return t1;
  }
};
signed main() {
  set<pair<long long, long long> > s;
  MergingSegmentTree seg;
  long long N;
  scanf("%lld", &N);
  long long ans = 0;
  for (long long i = 0; i < (N); i++) {
    long long a, b;
    scanf("%lld%lld", &a, &b);
    long long k = seg.build(b);
    auto it = s.lower_bound(pair<long long, long long>(a + 1, -1));
    if (it != s.begin()) {
      it--;
      if (it->first + seg.sz[it->second] >= a) {
        ans -= b * (a - it->first);
        ans -= seg.opt[it->second];
        seg.merge(it->second, k);
        tie(a, k) = *it;
        ans += seg.opt[k];
      } else {
        s.insert(pair<long long, long long>(a, k));
      }
    } else {
      s.insert(pair<long long, long long>(a, k));
    }
    while (true) {
      it = s.lower_bound(pair<long long, long long>(a + 1, -1));
      if (it == s.end()) break;
      if (a + seg.sz[k] >= it->first) {
        ans -= seg.sum[it->second] * (it->first - a);
        ans -= seg.opt[k];
        ans -= seg.opt[it->second];
        seg.merge(k, it->second);
        ans += seg.opt[k];
        s.erase(*it);
      } else
        break;
    }
    printf("%lld\n", ans);
  }
  return 0;
}
