题目大意

A和B玩游戏。一开始有n个pair, . 分三步：
(1) B首先选m个pair删掉;
(2) A从剩下的pair中取走一个，假设取走, 他的收益是;
(3) B从剩下的pair中取走一个，假设取走, 他的收益是.
A想要越大越好，B想要越小越好。问双方采取最优策略情况下，对所有满足的m，的值是多少。

解法

为了便于思考，不妨将删去若干个pair理解成选出若干个pair，所以第一步变成B首先选m个pair作为游戏局面，此时. （我们称第一步结束后选出的pair为一个局面）

考虑第3步B的策略，B一定是从剩下的pair中选最大的。然后我们考虑第2步A的策略。A有2个策略：1. 将最大的pair取走. 2. 不取最大的pair，那么就要取剩下的pair中最大的。

如果我们将最大的pair记为, 除去pair剩下的pair中最大的记为, 除去pair剩下的pair中最大的记为。那么A选择策略1得到的答案是, 选择策略2得到的的答案是，于是最终答案是. 当时选择策略1, 否则选择策略2.

现在我们来讨论第一步B的策略。

对任何一个局面来说，由四个值就能确定答案. 所以我们可以称为这个局面的特征值。

而这四个值涉及到的pair不会超过3个（是一个pair，可能在同个pair，也不能不在）。也就是说，如果我们将这三个pair之外的其他pair，逐个去掉，答案也不会改变。这样一来，我们可以得到结论，假设时，B有一个最优策略，答案是ans，那么当时，B也可以构造出答案为ans的策略。（用刚才的方法逐个去掉pair）

可以看到，的情况比较特殊，我们特判掉。如何求时的答案呢？很简单，将所有pair按从大到小排序，枚举选出的第一个pair，那么剩下的那个pair在后面选，由于，所以答案是，于是从剩下的数中选最大的即可。

下面我们求的情况。

不妨将问题转出成，枚举，问最多能选出多少个pair，使得局面的特征值是。记为最多能选出的pair的个数。那么这道题就是，我们求出后，用更新的答案。（打个标记即可，最后做个后缀Min）

于是我们把问题从“大小为m的所有局面中求最优答案”转化成“对某个答案求局面大小m的最大值”. 但是, 有n个，有n个，也有n个，总的状态数是啊！说明很多状态不必枚举。

我们先考虑枚举第一维，. 不妨首先将所有pair按照从大到小排序，这样枚举时，剩余的所有pair都是在这个pair的后面中选(）

固定后，从B的角度看，如果有得选择，肯定是希望越小越好，越大越好。那我们第二维枚举, 于是这时后面所有的的pair都能选择。注意到我们想让越大越好，所以肯定时把这个可以选择的pair（）全部选了，这样能尽量的大，局面大小也能尽量的大。所有可以直接确定。于是我们只用枚举的状态，但仍然太多了。

我们不妨用个二维表格来分析这的状态。第i行表示枚举为（注意数组已经按从大到小排好序了），第j列表示枚举的值为j.

单元格(i,j)的F值是1+“有多少个pair，满足”. 可见，对于每一行，从左到右，F值（最大的局面大小）是单调递增的。（随着上界的增加，能选的pair越来越多。）同时，对于每一行，从左到右，也是单调递增的，于是，对于每一行，一定是左边若干个单元格答案是策略1（答案是, 要求), 右边若干个单元格答案是策略2（答案是)

对于策略1的答案，由于从左到右会变大，所以会变小，所以就更优了。也就是说，在策略1的区域,对于同一行，如果我们从左往右移动，答案会变优，同时F值（最大的局面大小）也会变大。所以就没有必要考虑左边的状态了。也就是，在策略1的区域，同一行我们只需考虑最右的单元格。

对于策略2的答案, 对于同一列，固定，从上往下走，不断变小，所以答案不断变劣，同时F值会越来越小，于是同样地，在策略2的区域，对于同一列，只需考虑位置最上的那一个状态。
上图打勾的地方是需要计算的状态。

于是，我们就只需计算个状态的结果了，每一行要二分出策略1和策略2区域的分界点，而维护每个单元格对应的值，可以用个主席树。于是得到了复杂度 做法。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
const int INF = 1e9+7;
typedef pair<int,int> P;
#define x first
#define y second
P a[N];
int n;
int ans[N],numa[N],ida[N];
void Mini(int &a, int b) {
    if (b < a) a = b;
}
void Maxi(int &a, int b) {
    if (b > a) a = b;
}

struct Node {
    int cnt,chl,chr;
}T[N*21];
#define cnt(v) T[v].cnt
#define chl(v) T[v].chl
#define chr(v) T[v].chr
int tot;
void add(int &o, int last,int x, int l=0, int r=n) {
    o=++tot;
    T[o]=T[last];
    ++cnt(o);
    if (l+1==r) return;
    int mid=(l+r)/2;
    if (x < mid) add(chl(o), chl(last), x, l, mid);
    else add(chr(o), chr(last), x, mid, r);
}
int qcnt;
int query(int v1, int v2, int L, int R, int l=0, int r=n) { // [L,R)
    ++qcnt;
    if (R<=l || r<=L) return -1;
    if (cnt(v2)-cnt(v1)==0) return -1;
    if (l+1==r) return l;
    int mid=(l+r)/2;
    int q=query(chl(v1),chl(v2),L,R,l,mid);
    if (q!=-1) return q;
    return query(chr(v1),chr(v2),L,R,mid,r);
}
int rt[N];
vector<int> vec[N];
int sz;
inline int lowbit(int i) {
    return i&-i;
}
struct BIT {
    int dat[N];
    int sum(int i) {
        ++i;
        int res=0;
        for (; i > 0; i -= lowbit(i)) res+=dat[i];
        return res;
    }
    void add(int i, int x) {
        ++i;
        for (; i < N; i += lowbit(i)) dat[i] += x;
    }
}bit;
void update_ans(int m, int val) {
    if (m >= 3 && m <= n) Mini(ans[m],val);
}

bool test(int x, int i, int s) {
    int q=query(0,rt[x],i+1,n);
    if (q==-1) return false;
    return a[q].y>=s-numa[x];
}

int getpos(int i, int s) {
    int l=-1,r=sz;
    while (l+1<r) {
        int mid=(l+r)/2;
        if (test(mid,i,s)) r=mid;
        else l=mid;
    }
    return l;
}

int main() {
    scanf("%d",&n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &a[i].x, &a[i].y);
        numa[i]=a[i].x;
    }
    fill(ans,ans+n+1,INF);
    sort(a,a+n, [](const P&i, const P&j) {
        return i.x+i.y<j.x+j.y;
    });
    int mxb=a[0].y;
    for (int i = 1; i < n; i++) {
        Mini(ans[2], a[i].x-mxb);
        Maxi(mxb, a[i].y);
    }
    sort(a,a+n, [](const P&i, const P&j) {
        return i.y>j.y;
    });
    sort(numa,numa+n);
    sz=unique(numa,numa+n)-numa;
    for (int i = 0; i < n; i++) {
        ida[i]=lower_bound(numa,numa+sz,a[i].x)-numa;
        vec[ida[i]].push_back(i);
        bit.add(ida[i],1);
    }
    for (int i = 0; i < sz; i++) {
        if (i > 0) rt[i]=rt[i-1];
        for (auto x: vec[i]) {
            add(rt[i],rt[i],x);
        }
    }
    int mxa=sz-1;
    for (int i=0; i < n; i++) {
        bit.add(ida[i],-1);
        int pos=getpos(i,a[i].x+a[i].y);
        if (pos>=0) {
            int q=query(0,rt[pos],i+1,n);
            if (q!=-1) {
                update_ans(1+bit.sum(pos),a[i].x-a[q].y);
            }
        }
        for (int x=mxa;x>pos&&x>=0;x--) {
            update_ans(1+bit.sum(x), numa[x]-a[i].y);
        }
        Mini(mxa,pos);
    }
    for (int i = n-1; i >= 3; i--) Mini(ans[i], ans[i+1]);
    for (int i=n;i>=2;i--) printf("%d\n",ans[i]);
}