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 inf = 1e9 + 7;
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <class A, class B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <class A>
string to_string(A v) {
  int f = 1;
  string r("{");
  for (auto x : v) {
    if (!f) r += ", ";
    f = 0;
    r += to_string(x);
  }
  return r + "}";
}
void debug_out() { cout << endl; }
template <class Head, class... Tail>
void debug_out(Head H, Tail... T) {
  cout << " " << to_string(H);
  debug_out(T...);
}
struct node {
  int l, r, count;
  long long sum, ans;
  node(int l = 0, int r = 0, int count = 0, long long sum = 0,
       long long ans = 0)
      : l(l), r(r), count(count), sum(sum), ans(ans) {}
};
vector<node> T(1);
int n;
map<int, int> mp;
long long ans = 0;
int make_node() {
  T.emplace_back();
  return int(T.size()) - 1;
}
int upd(int no, int l, int r, int b) {
  T[no].count += 1;
  T[no].sum += b;
  if (l == r) {
    return no;
  }
  int m = (l + r) / 2;
  if (b <= m) {
    int bc = upd(make_node(), l, m, b);
    T[no].l = bc;
  } else {
    int bc = upd(make_node(), m + 1, r, b);
    T[no].r = bc;
  }
  return no;
}
int merge(int x, int y, int l, int r) {
  if (!x or !y) {
    return x ^ y;
  }
  int m = (l + r) / 2;
  assert(l != r);
  ans += T[T[x].r].count * T[T[y].l].sum;
  ans += T[T[y].r].count * T[T[x].l].sum;
  int bc = merge(T[x].l, T[y].l, l, m);
  T[x].l = bc;
  bc = merge(T[x].r, T[y].r, m + 1, r);
  T[x].r = bc;
  T[x].sum = T[T[x].l].sum + T[T[x].r].sum;
  T[x].count = T[T[x].l].count + T[T[x].r].count;
  return x;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  map<int, int> mp;
  mp[-1] = 0;
  mp[1e9] = 0;
  cin >> n;
  for (auto _ = (1); _ <= (n); ++_) {
    int a, b;
    cin >> a >> b;
    auto it = --mp.upper_bound(a);
    int c = make_node();
    c = upd(c, 1, n, b);
    int L = it->first + T[it->second].count;
    int pos = a;
    if (L >= a) {
      ans -= (a - it->first) * 1LL * b;
      c = merge(it->second, c, 1, n);
      pos = it->first;
    }
    mp[pos] = c;
    it = --mp.upper_bound(a);
    L = it->first + T[it->second].count;
    auto it2 = it;
    ++it2;
    if (L >= it2->first) {
      ans -= (it2->first - it->first) * T[it2->second].sum;
      c = merge(c, it2->second, 1, n);
      mp.erase(it2->first);
    }
    mp[pos] = c;
    cout << ans << "\n";
  }
  return 0;
}
