嗷嗷嗷校内模拟赛出了此题被细节搞死了。

首先我们按 $a$ 从小到大排序，这样对于前 $i$ 个元素，$a$ 的最大值就是 $a_i$。
以下记给第一位朋友买礼物的商店为集合 $A$，给第二位朋友买礼物的商店为集合 $B$。我们就钦定集合 $A$ 中，$a$ 的最大值就是 $a_i$。
我们可以把所有 $x(1 \le x \le n)$ 分成三组：

1. $a_x < a_i$。这些 $x$ 可以属于集合 $A$，也可以属于集合 $B$，没有限制。
2. $a_x=a_i$。这些 $x$ 同样既可以属于集合 $A$，也可以属于集合 $B$，但是至少要有一个属于集合 $A$。
3. $a_x>a_i$。这些 $x$ 只能属于集合 $B$。

现在我们的问题就变成了如何合理分配 $a_x\le a_i$ 的 $x$ 们，使得集合 $B$ 中的 $b_{\max}$ 最接近 $a_i$。

$a$ 相同的 $i$ 我们可以一起考虑，因此我们可以令当前的 $i$ 是满足 $a_x \le a_i$ 的最大的 $x$（也就是说，$a_{i+1} > a_i$）。
这样第三组 $x$ 就变成了区间 $[i+1,n]$。这一段的 $b$ 是不可避免要计算的，因此可以先算出来。
此时如果 $b_{\max}$ 已经 $\ge a_i$ 了，那么不用往下考虑了，因为已经无法令 $b_{\max}$ 更接近 $a_i$ 了（最大值是单调递增的嘛）。
否则就考虑在 $[1,i]$ 中查找最接近 $a_i$ 的 $b_x$。我们可以维护一个 set，set 中查前驱后继是很好的。
但是要注意：

• 如果 $a_x=a_i$ 的 $x$ 不止一个，那么直接找就行了。因为如果我们不幸找到了 $b_i$，那么可以用别的 $a_x$ 来匹配 $b_i$。
• 但是如果 $a_x=a_i$ 的 $x$ 只有一个，那么需要特判找到的 $b$ 是不是 $b_i$。一个小方法是先在 set 中删掉 $b_i$，再查前驱后继，查完再塞回去。
• set 要开 multiset！！！

把 $i$ 从 $1$ 到 $n$ 扫一遍就结束了。

以下代码带有一些校内模拟赛的注释。
CF 的数据较为强悍，可以去 CF 交一发。
【可以扩展思考：如果要求最大值怎么做？】

#include<set>
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
pair<int,int>s[500005];
priority_queue<pair<int,int>>heap;
int n,as1=1e9+5,as2;multiset<int>fnd;
void sol_as1()
{
    for(int i=1;i<=n;i++) heap.push({s[i].second,s[i].first});
    //按b从大到小排序
    for(int i=1;i<=n;i++)
    {
        int cnt=0,a=s[i].first;
        while(i!=n&&a==s[i+1].first)
        fnd.insert(s[i].second),i++,cnt++;
        fnd.insert(s[i].second),cnt++;
        while((!heap.empty())&&heap.
        top().second<=a) heap.pop();
        if(!heap.empty())
        {
            int bmx=heap.top().first;if(bmx>=a)
            {as1=min(as1,bmx-a);continue;}
            as1=min(as1,a-bmx);
        }
        if(cnt>1)
        {
            auto x=fnd.lower_bound(a);
            if(x!=fnd.end()) as1=min(as1,(*x)-a);//>=x中取最小
            //——等一下它不会没超过bmx吧？但如果如此那么fnd<=bmx<=a，显然不会统计。
            if(x!=fnd.begin()) x=prev(x),as1=min(as1,a-(*x));continue;
        }/*auto x=fnd.lower_bound(a+1);
        //如果a只有一个，那么fnd中有且仅有一个a，只要取到比它大就好。
        // if(x!=fnd.end()&&((*x).second!=s[i].first
        // ||(*x).first!=s[i].second)) as1=min(as1,(*x)-a);
        x=fnd.lower_bound(a);if(x==fnd.begin()) continue;
        x=prev(x),as1=min(as1,a-(*x));*/
        fnd.erase(fnd.find(s[i].second));
        auto x=fnd.lower_bound(a);
        if(x!=fnd.end()) as1=min(as1,(*x)-a);
        if(x!=fnd.begin()) x=prev(x),as1=min(as1,a-(*x));
        fnd.insert(s[i].second);
    }
}
int main()
{
    // freopen("manyhacks.in","r",stdin);
    // freopen("manyhacks.out","w",stdout);
    scanf("%d",&n);for(int i=1;i<=n;i++)
    scanf("%d%d",&s[i].first,&s[i].second);
    sort(s+1,s+n+1);sol_as1();
    printf("%d",as1);
}//注意大样例很水。虽然自己生成的数据疑似可能也很水。
//注意捆绑测试。