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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const long long BIG = 400000000000000000ll;

struct node {
  pair<long long, long long> p;  // best unused line before time int_time
  bool side;  // 0 means that p is a left son
  long long sum;  // of used in the subtree
  int num;  // of used in the subtree
  long long int_time;  // how big .num on the left side has to be for an intersection
  long long p_num, p_sum;  // used by p (the best function in the subtree)
};

node p[1<<21];
int n;
long long ans;
int K = 1;

bool comp1(int a, int b) {
  return p[a].p < p[b].p;
}

void fix_up(const int i, const int pos) {  // 1 <= i < K, lower levels are ok for this pos (= .num on the left)
  p[i].sum = p[2*i].sum + p[2*i+1].sum;
  p[i].num = p[2*i].num + p[2*i+1].num;
  long long a[2];
  a[0] = (pos + p[2*i].p_num) * p[2*i].p.first + p[2*i].p.second + p[2*i+1].sum + p[2*i].p_sum;
  a[1] = (pos + p[2*i].num + p[2*i+1].p_num) * p[2*i+1].p.first + p[2*i+1].p.second + p[2*i+1].p_sum;
  p[i].int_time = min(p[2*i].int_time, p[2*i+1].int_time - p[2*i].num);
  if (a[0] <= a[1]) {  // use right p
    p[i].p = p[2*i+1].p;
    p[i].p_sum = p[2*i+1].p_sum;
    p[i].p_num = p[2*i].num + p[2*i+1].p_num;
    p[i].side = 1;
  }
  else {
    p[i].p = p[2*i].p;
    p[i].p_sum = p[2*i].p_sum + p[2*i+1].sum;
    p[i].p_num = p[2*i].p_num;
    p[i].side = 0;

    long long t = n;
    if (p[2*i].p.first < p[2*i+1].p.first) {
      t = ((p[2*i].p.second - p[2*i+1].p.second) + (p[2*i].p_num * p[2*i].p.first - (p[2*i].num + p[2*i+1].p_num) * p[2*i+1].p.first) + \
          + (p[2*i].p_sum + p[2*i+1].sum - p[2*i+1].p_sum) + (p[2*i+1].p.first - p[2*i].p.first - 1)) /
        (p[2*i+1].p.first - p[2*i].p.first);
    }
    if (t <= 0 || t > n)
      t = n;
    p[i].int_time = min(t, p[i].int_time);
  }
}

int counter;

void fix_int(const int i, const int pos) {  // for i < K
  if (2*i < K && p[2*i].int_time <= pos)
    fix_int(2*i, pos);
  if (2*i+1 < K && p[2*i+1].int_time <= pos + p[2*i].num)
    fix_int(2*i+1, pos + p[2*i].num);
  fix_up(i, pos);
}

long long best(const int i, int pos, long long sum) {
  if (i >= K) {  // found best !
    long long a = sum + pos * p[i].p.first + p[i].p.second;
    p[i].sum = p[i].p.first;
    p[i].num = 1;
    p[i].p.second = -BIG;
    return a;
  }
  if (p[i].int_time <= pos) {
    fix_int(i, pos);
  }
  if (p[i].side == 0) {
    long long b = best(2*i, pos, sum + p[2*i+1].sum);
    fix_int(i, pos);
    return b;
  }
  else {
    long long b = best(2*i+1, pos + p[2*i].num, sum);
    fix_int(i, pos);
    return b;
  }
}

int main() {
  scanf("%d", &n);
  int t[n];
  K = 2;
  while (K < n)
    K <<= 1;

  for (int i = 0; i < n; ++i) {
    long long a, b;
    scanf("%lld %lld", &a, &b);
    p[i].p.first = a;
    p[i].p.second = b;
    t[i] = i;
  }

  sort(t, t+n, comp1);
  for (int i = 0; i < n; ++i) {
    p[K+i].p = p[t[i]].p;
    p[K+i].int_time = n;
  }
  for (int i = n; i < K; ++i) {
    p[K+i].p.first = 1000000;
    p[K+i].p.second = -BIG;
    p[K+i].int_time = n;
  }

  for (int i = K - 1; i > 0; --i) {
    fix_up(i, 0);
  }

  for (int i = 0; i < n; ++i) {
    fix_int(1, 0);
    ans += best(1, 0, 0);
    printf("%lld\n", ans);
  }
    
  return 0;
}