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 MAXN = 2e5 + 5;
template <typename T>
struct fenwick {
  unordered_map<int, T> f;
  void update(int x, T val) {
    for (; x < MAXN; x += x & -x) f[x] += val;
  }
  T get(int x) {
    T res = 0;
    for (; x; x -= x & -x)
      if (f.find(x) != f.end()) res += f[x];
    return res;
  }
};
int N;
int dad[2 * MAXN];
int lft[2 * MAXN], rig[2 * MAXN];
fenwick<int> cnt[2 * MAXN];
fenwick<long long> sum[2 * MAXN];
vector<int> vals[2 * MAXN];
long long tot[2 * MAXN];
bool bio[2 * MAXN];
long long ans;
void init() {
  for (int i = 0; i < 2 * MAXN; i++) dad[i] = lft[i] = rig[i] = i;
}
int find(int x) { return dad[x] == x ? x : dad[x] = find(dad[x]); }
void join(int x, int y) {
  x = find(x);
  y = find(y);
  if (rig[x] - lft[x] > rig[y] - lft[y]) swap(x, y);
  ans -= tot[x] + tot[y];
  tot[y] -= (long long)lft[y] * sum[y].get(MAXN - 1);
  dad[x] = y;
  lft[y] = min(lft[y], lft[x]);
  rig[y] = max(rig[y], rig[x]);
  for (auto it : vals[x]) {
    tot[y] += sum[y].get(it - 1);
    vals[y].push_back(it);
  }
  for (auto it : vals[x]) {
    cnt[y].update(MAXN - it, 1);
    sum[y].update(it, it);
  }
  long long old = tot[y];
  for (auto it : vals[x]) tot[y] += (long long)it * cnt[y].get(MAXN - it - 1);
  tot[y] += (long long)lft[y] * sum[y].get(MAXN - 1);
  ans += tot[y];
}
void modify(int a, int b) {
  ans -= (long long)a * b;
  if (bio[a]) a = rig[find(a)] + 1;
  bio[a] = true;
  cnt[a].update(MAXN - b, 1);
  sum[a].update(b, b);
  tot[a] = (long long)a * b;
  ans += tot[a];
  vals[a].push_back(b);
  if (bio[a - 1]) join(a - 1, a);
  if (bio[a + 1]) join(a + 1, a);
}
int main() {
  init();
  scanf("%d", &N);
  while (N--) {
    int a, b;
    scanf("%d%d", &a, &b);
    modify(a, b);
    printf("%lld\n", ans);
  }
  return 0;
}
