1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
#include <cstdio>
#include <algorithm>

#define SZ(x) ((x) ? (x)->size : 0)

inline long long read() {
  static char ch;
  while ((ch = getchar()) < '0' || ch > '9');
  long long res = ch - 48;
  while ((ch = getchar()) >= '0' && ch <= '9') res = res * 10 + ch - 48;
  return res;
}

inline int Rand() {
  static int x = 233;
  return x += x << 2 | 1;
}

const int N = 1e6 + 5;
const long long INF = 1ll << 50;
int n, m;
int a[N], id[N];
long long b[N];
unsigned long long ans;
struct node {
  node *fa, *lc, *rc;
  int size;
  long long add, delta;
  
  void Splay(node *tar);
  int dir() const { return fa->rc == this; }
  void update() { size = SZ(lc) + SZ(rc) + 1; }
  
  void Release() {
    if (!add) return ;
    if (lc) lc->add += add, lc->delta += add;
    if (rc) rc->add += add, rc->delta += add;
    add = 0; 
  }

  void Rotate() {
    static node *u, *v, *w, *b;
    u = this, v = fa, w = v->fa, b = (v->lc == u) ? u->rc : u->lc;
    fa = w, v->fa = u, (b) ? b->fa = v : 0;
    if (w) (w->lc == v ? w->lc : w->rc) = u;
    if (v->lc == u) u->rc = v, v->lc = b;
    else u->lc = v, v->rc = b;
    v->update();
  }
} used[N], *pool = used, *rt;

void node::Splay(node *tar) {
  while (fa != tar) {
    if (fa->fa != tar)
      (dir() == fa->dir() ? fa : this)->Rotate();
    Rotate();
  }
  update();
  if (!tar) rt = this;
}

void find(int x) {
  static node *u, *v, *w;
  int nows = 0;
  u = v = rt;
  while (u) {
    u->Release();
    if ((long long)(nows + SZ(u->lc)) * a[x] + b[x] < u->delta) nows += SZ(u->lc) + 1, u = u->rc;
    else v = u, u = u->lc;
  }
  (u = v)->Splay(NULL);
  (w = pool++)->delta = (long long)SZ(u->lc) * a[x] + b[x];
  
  if (!u->lc) (u->lc = w)->fa = u;
  else {
    v = u->lc;
    while (v->Release(), v->rc) v = v->rc;
    (v->rc = w)->fa = v;
  }
  w->Splay(NULL);
  w->rc->add += a[x], w->rc->delta += a[x];
}

void dfs(node *u) {
  static long long sum = 0;
  u->Release();
  if (u->lc) dfs(u->lc); 
  sum += u->delta;
  if (++m <= n) printf("%lld\n", sum);
  if (u->rc) dfs(u->rc);
}

inline bool cmp(const int &x, const int &y) {
  return a[x] < a[y];
}

int main() {
  n = read();
  for (int i = 1; i <= n; ++i)
    a[i] = read(), b[i] = read(), id[i] = i;
  std::sort(id + 1, id + n + 1, cmp);

  rt = pool++;
  rt->size = 1, rt->delta = -INF;
  for (int j = 1; j <= n; ++j) find(id[j]);
  dfs(rt);
  return 0;
}