y总讲解-链表法（有些小坑需要注意，根据测试数据，设置的哨兵需要是long long类型。在差值相等时，取较小的那个数，而非序号较小的。

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10;
typedef long long LL;
typedef pair<LL, int> pr;

int l[N], r[N], t[N];
pr ns[N], ans[N];

int main()
{
    int n;
    scanf("%d", &n);
    for(int i=1;i<=n;++i) scanf("%ld", &ns[i].first), ns[i].second = i;

    sort(ns+1, ns+n+1);
    ns[0] = {-3e9,0}, ns[n+1] = {3e9,n+1};
    for(int i=1;i<=n;++i)
    {
        l[i] = i-1, r[i] = i+1;
        t[ns[i].second] = i;
    }

    for(int i=n;i>=2;--i)
    {
        int j=t[i], left=l[j], right=r[j];
        LL lv=abs(ns[left].first - ns[j].first), rv=abs(ns[right].first - ns[j].first);
        if(lv<=rv) ans[i] = {lv, ns[left].second};
        else ans[i] = {rv, ns[right].second};

        l[right]=left, r[left]=right;
    }

    for(int i=2;i<=n;++i)
        printf("%d %d\n", ans[i].first, ans[i].second);

    return 0;
}

SET

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

typedef long long LL;
typedef pair<LL, int> pr;

set<pr> sset;

int main()
{
    int n, x;
    scanf("%d", &n);
    sset.insert({-3e9,0}), sset.insert({3e9,0});
    for(int i=1; i<=n; ++i)
    {
        scanf("%d", &x);
        if(i>1)
        {
            auto it = sset.upper_bound({x,0});
            auto jt=it; --jt;
            LL lv=x-jt->first, rv=it->first-x;
            if(lv<=rv) printf("%d %d\n", lv, jt->second);
            else printf("%d %d\n", rv, it->second);
        }
        sset.insert({x,i});
    }

    return 0;
}