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;
int n, INF = 1e9, cur;
vector<int> U[201000];
map<int, int> Map[201000];
struct point {
  int b, e, num;
  bool operator<(const point &p) const {
    return b != p.b ? b < p.b : e != p.e ? e < p.e : num < p.num;
  }
};
struct PPP {
  int ck, num, x;
};
vector<PPP> V[201000];
set<point> Set;
void Move(int a, int b) {
  for (auto &x : U[a]) {
    U[b].push_back(x);
    V[cur].push_back({2, b, x});
  }
  V[cur].push_back({3, a, 0});
}
void Put(int a, int b, int num) {
  cur = num;
  Set.insert({a, a, num});
  V[cur].push_back({1, num, a});
  V[cur].push_back({2, num, b});
  U[num].push_back(b);
  auto it = Set.find({a, a, num});
  while (it != Set.begin()) {
    auto it2 = it;
    it2--;
    if (it2->e + 1 >= it->b) {
      int sz2 = it2->e - it2->b + 1;
      int sz = it->e - it->b + 1;
      int num1 = it->num;
      int num2 = it2->num;
      if (sz > sz2) swap(num2, num1);
      Move(num1, num2);
      point tp = {it2->b, it2->b + (sz2 + sz) - 1, num2};
      V[cur].push_back({1, num2, it2->b});
      Set.erase(it);
      Set.erase(it2);
      Set.insert(tp);
      it = Set.find(tp);
    } else
      break;
  }
  while (1) {
    auto it2 = it;
    it2++;
    if (it2 == Set.end()) break;
    if (it->e + 1 >= it2->b) {
      int sz2 = it2->e - it2->b + 1;
      int sz = it->e - it->b + 1;
      int num1 = it->num;
      int num2 = it2->num;
      if (sz > sz2) swap(num2, num1);
      Move(num1, num2);
      point tp = {it->b, it->b + (sz2 + sz) - 1, num2};
      V[cur].push_back({1, num2, it->b});
      Set.erase(it);
      Set.erase(it2);
      Set.insert(tp);
      it = Set.find(tp);
    } else
      break;
  }
}
long long BB[201000 * 60], Res;
int BB2[201000 * 60];
int SZ[201000], bb[201000];
long long *BIT[201000];
long long SS[201000], RR[201000], CCC[201000];
int *BIT2[201000];
struct AA {
  int a, b;
} w[201000];
void Add(int pv, int x, long long b) {
  while (x <= SZ[pv]) {
    BIT[pv][x] += b;
    x += (x & -x);
  }
}
long long Sum(int pv, int x) {
  long long r = 0;
  while (x) {
    r += BIT[pv][x];
    x -= (x & -x);
  }
  return r;
}
void Add2(int pv, int x, int b) {
  while (x <= SZ[pv]) {
    BIT2[pv][x] += b;
    x += (x & -x);
  }
}
int Sum2(int pv, int x) {
  int r = 0;
  while (x) {
    r += BIT2[pv][x];
    x -= (x & -x);
  }
  return r;
}
int main() {
  int i, a, b;
  Set.insert({-10, -10});
  Set.insert({INF, INF});
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    scanf("%d%d", &a, &b);
    Put(a, b, i);
    w[i] = {a, b};
  }
  int s = 0;
  for (i = 1; i <= n; i++) {
    if (!U[i].empty()) {
      sort(U[i].begin(), U[i].end());
      for (int j = 0; j < U[i].size(); j++) Map[i][U[i][j]] = j + 1;
    }
    BIT[i] = BB + s;
    BIT2[i] = BB2 + s;
    SZ[i] = U[i].size();
    s += SZ[i] + 1;
  }
  for (i = 1; i <= n; i++) {
    Res -= 1ll * w[i].a * w[i].b;
    for (auto &t : V[i]) {
      Res -= RR[t.num];
      if (t.ck == 1) {
        RR[t.num] -= SS[t.num] * bb[t.num];
        bb[t.num] = t.x;
        RR[t.num] += SS[t.num] * bb[t.num];
      }
      if (t.ck == 2) {
        RR[t.num] -= SS[t.num] * bb[t.num];
        int xx = Map[t.num][t.x];
        RR[t.num] += Sum(t.num, xx);
        Add(t.num, xx, t.x);
        RR[t.num] += 1ll * t.x * (CCC[t.num] - Sum2(t.num, xx));
        Add2(t.num, xx, 1);
        SS[t.num] += t.x;
        RR[t.num] += SS[t.num] * bb[t.num];
        CCC[t.num]++;
      }
      if (t.ck == 3) RR[t.num] = 0;
      Res += RR[t.num];
    }
    printf("%lld\n", Res);
  }
}
