题解 | #单调栈结构(进阶)#

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

const int MAXN = 1000001;
int arr[MAXN];
int st[MAXN];
int ans[MAXN][2];
int n, r;

void compute() {
    r = 0;
    int cur;

    for(int i = 0; i < n; i++){
        while(r > 0 && arr[st[r - 1]] >= arr[i]){
            cur = st[--r];
            ans[cur][0] = r > 0 ? st[r - 1] : -1;
            ans[cur][1] = i;
        }
        st[r++] = i;
    }

    while(r > 0){
        cur = st[--r];
        ans[cur][0] = r > 0 ? st[r - 1] : -1;
        ans[cur][1] = -1;
    }

    for(int i = n - 2; i >= 0; i--){
        if(ans[i][1] != -1 && arr[ans[i][1]] == arr[i]){
            ans[i][1] = ans[ans[i][1]][1];
        }
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

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

        compute();
        for(int i = 0; i < n; i++){
            cout << ans[i][0] << " " << ans[i][1] << endl;
        }
    }

    return 0;
}