yxc提到但未讲的set解法，online

#include <iostream>
#include <algorithm>
#include <set>
#include <limits.h>
using namespace std;

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

const int N = 100010;
int n;
PII  ans[N];
int a[N];

void calMinAdjacent() {
    set<pair<int, int>> mySet;
    mySet.insert({a[0], 0});
    for (int i = 1; i < n; i++) {
        int cur = a[i];
        auto it = mySet.lower_bound({cur, i});
        int temp = INT_MAX;
        int index = -1;
        if (it != mySet.end()) {
            temp = min(temp, it->first - cur);
            index = it->second;
        }
        if (it != mySet.begin()) {
            it--;
            if (cur - it->first < temp) {
                temp = cur - it->first;
                index = it->second;
            } else if (cur - it->first == temp) {
                if (a[it->second] < a[index]) {
                    index = it->second;
                }
            }
        }

        ans[i] = {temp, index};
        mySet.insert({cur, i});
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        cin >> a[i];
    }

    calMinAdjacent();
    for (int i = 1; i < n; i ++ ) cout << ans[i].first << ' ' << ans[i].second + 1 << endl;
    return 0;
}

yxc视频同款不同色解法，不用链表，用map。offline

typedef long long LL;
typedef pair<LL, int> PII;
const int N = 100010;

int n;
int a[N];
PII ans[N];
map<LL, int> myMap = {{-3e9, -1}, {3e9, -1}};

void calMinAdjacent() {
    for (int i = n - 1; i >= 0; i--) {
        int x = a[i];

        auto it = myMap.lower_bound(x);
        auto it2 = it, it1 = it;
        it1--, it2++;
        if (x - it1->first <= it2->first - x) {
            ans[i] = {x - it1->first, it1->second};
        } else {
            ans[i] = {it2->first - x, it2->second};
        }

        myMap.erase(x);
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        cin >> a[i];
        myMap[a[i]] = i;
    }
    calMinAdjacent();
    for (int i = 1; i < n; i ++ ) cout << ans[i].first << ' ' << ans[i].second + 1 << endl;
    return 0;
}