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

import sys

MAXN = 1000001
arr = [0] * MAXN
stack = [0] * MAXN
ans = [[-1, -1] for _ in range(MAXN)]

def compute(n, arr, stack, ans):
    r = 0
    for i in range(n):
        while r > 0 and arr[stack[r - 1]] >= arr[i]:
            cur = stack[r - 1]
            r -= 1
            ans[cur][0] = stack[r - 1] if r > 0 else -1
            ans[cur][1] = i
        stack[r] = i
        r += 1

    while r > 0:
        cur = stack[r - 1]
        r -= 1
        ans[cur][0] = stack[r - 1] if r > 0 else -1
        ans[cur][1] = -1

    for i in range(n - 2, -1, -1):
        if ans[i][1] != -1 and arr[ans[i][1]] == arr[i]:
            ans[i][1] = ans[ans[i][1]][1]

def main():
    input_buffer = sys.stdin.read().splitlines()
    output_buffer = []

    line_index = 0
    while line_index < len(input_buffer):
        n = int(input_buffer[line_index])
        line_index += 1
        values = list(map(int, input_buffer[line_index].strip().split()))
        line_index += 1

        arr[:n] = values

        compute(n, arr, stack, ans)
        output_buffer.extend(f"{ans[i][0]} {ans[i][1]}" for i in range(n))

    sys.stdout.write('\n'.join(output_buffer))

if __name__ == "__main__":
    main()