[解释] 采用链表做法。将值用pair存，first为原数组的值，second为原来位置，这样再排序后不 会丢失位置。只需一次for就可以得到原数组再排序后的位置，同时根据排序后的单调关系建立链表。我们根据原数组从后往前的顺序去链表中找答案，可以很简单的得到答案一定出现在相邻的两个节点里（这里有个要求是如果pre节点和nxt节点得到的答案相同优先选pre节点）。随后删去这个节点保证下一个节点在找答案时整个链表内的所有节点在原数组中都在这个节点前面，也就是j < i。用pair存一下答案然后输出就可以了。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define xx first
#define yy second
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
const ll N = 1e5+7;
const ll inf = 0x3f3f3f3f;

ll n, b[N];
PII a[N], ans[N];

struct Node{
    ll v;
    ll pre, nxt;
    ll id;
}c[N];
//定义用于比较pair的函数，可以在min中传入
auto cmp = [](const PII &a, const PII &b){
    return a.xx < b.xx;
};

void solve()
{   
    cin >> n;
    for(ll i = 1; i <= n; i ++){
        cin >> a[i].xx;
        a[i].yy = i;
    }
    sort(a + 1, a + 1 + n);
    ll hh = 1, tt = n;
    for(ll i = 1; i <= n; i ++){
        b[a[i].yy] = i;
        c[i].v = a[i].xx;
        c[i].id = a[i].yy;
        c[i].pre = i - 1;
        c[i].nxt = i + 1;
    }
    for(ll i = n; i > 1; i --){
        PII res = {inf * inf, tt + 1};
        ll x = b[i];
        ll pre = c[x].pre, nxt = c[x].nxt;
        if(pre >= hh) res = min(res, {abs(c[x].v - c[pre].v), c[pre].id}, cmp);
        if(nxt <= tt) res = min(res, {abs(c[x].v - c[nxt].v), c[nxt].id}, cmp);
        ans[i] = res;
        c[pre].nxt = nxt;
        c[nxt].pre = pre;
    }
    for(ll i = 2; i <= n; i ++){
        cout << ans[i].xx << ' ' << ans[i].yy << '\n';
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll tt = 1;
    // cin >> tt;
    while(tt --) solve();
    return 0;
}