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 T>
inline bool upmin(T &x, T y) {
  return y <= x ? x = y, 1 : 0;
}
template <typename T>
inline bool upmax(T &x, T y) {
  return x <= y ? x = y, 1 : 0;
}
const long double eps = 1e-9;
const long double pi = acos(-1);
const int oo = 1 << 30;
const long long loo = (1ll << 62) - 1;
const int MAXN = 400005;
const int MX = 400000;
const int INF = 0x3f3f3f3f;
namespace FastIO {
constexpr int SIZE = (1 << 21) + 1;
int num = 0, f;
char ibuf[SIZE], obuf[SIZE], que[65], *iS, *iT, *oS = obuf,
                                                *oT = obuf + SIZE - 1, c;
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char c) {
  *oS++ = c;
  if (oS == oT) flush();
}
inline void getc(char &c) {
  for (c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++);
       !isalpha(c) && c != EOF;
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    ;
}
inline void reads(char *st) {
  char c;
  int n = 0;
  getc(st[++n]);
  for (c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++);
       isalpha(c);
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    st[++n] = c;
  st[++n] = '\0';
}
template <class I>
inline void read(I &x) {
  for (f = 1, c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-') f = -1;
  for (x = 0; c >= '0' && c <= '9';
       c = (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    x = (x << 3) + (x << 1) + (c & 15);
  x *= f;
}
template <class I>
inline void print(I x) {
  if (x < 0) putc('-'), x = -x;
  if (!x) putc('0');
  while (x) que[++num] = x % 10 + 48, x /= 10;
  while (num) putc(que[num--]);
}
inline void putstr(string st) {
  for (int i = 0; i < (int)st.size(); ++i) putc(st[i]);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_Flusher_;
}  // namespace FastIO
using FastIO ::print;
using FastIO ::putc;
using FastIO ::putstr;
using FastIO ::read;
using FastIO ::reads;
long long s[MAXN * 20], ans = 0;
int sz[MAXN * 20], ls[MAXN * 20], rs[MAXN * 20], f[MAXN], rt[MAXN], R[MAXN],
    nodenum = 0;
int Insert(int x, int l, int r, int y) {
  if (!x) x = ++nodenum;
  if (l == r) {
    sz[x] = 1, s[x] = y;
    return x;
  }
  int mid = (l + r) >> 1;
  if (y <= mid)
    ls[x] = Insert(ls[x], l, mid, y);
  else
    rs[x] = Insert(rs[x], mid + 1, r, y);
  s[x] = s[ls[x]] + s[rs[x]];
  sz[x] = sz[ls[x]] + sz[rs[x]];
  return x;
}
int Merge(int x, int y) {
  if (!x || !y) return x | y;
  ans -= s[ls[x]] * sz[rs[x]] + s[ls[y]] * sz[rs[y]];
  ls[x] = Merge(ls[x], ls[y]);
  rs[x] = Merge(rs[x], rs[y]);
  ans += s[ls[x]] * sz[rs[x]], sz[x] += sz[y], s[x] += s[y];
  return x;
}
int find(int x) { return f[x] == x ? f[x] : f[x] = find(f[x]); }
void solve(int x, int y) {
  x = find(x), y = find(y), f[y] = x;
  ans -= s[rt[x]] * x + s[rt[y]] * y;
  rt[x] = Merge(rt[x], rt[y]);
  ans += s[rt[x]] * x;
  R[x] = R[y];
}
signed main() {
  int n;
  read(n);
  for (int i = 1; i <= MX; ++i) f[i] = i, R[i] = i;
  for (int i = 1; i <= n; ++i) {
    int x, y;
    read(x), read(y);
    int t = rt[x] ? R[find(x)] + 1 : x;
    ans -= 1ll * x * y;
    rt[t] = Insert(rt[t], 1, n, y);
    ans += 1ll * t * y;
    if (rt[t - 1]) solve(t - 1, t);
    if (rt[t + 1]) solve(t, t + 1);
    print(ans), putc('\n');
  }
  return 0;
}
