单调栈结构(进阶)

# 用list模拟单调栈
n = int(input())
arr = [int(k) for k in input().split()]
left = [-1 for _ in range(n)]
stk = []
# 左向右
for i in range(n):
    while stk and arr[stk[-1]] >= arr[i]:
        stk.pop()
    if stk:
        left[i] = stk[-1]
    stk.append(i)
right = [-1 for _ in range(n)]
stk = []
# 右向左
for i in range(n-1, -1, -1):
    while stk and arr[stk[-1]] >= arr[i]:
        stk.pop()
    if stk:
        right[i] = stk[-1]
    stk.append(i)
for i in range(n):
    print(f"{left[i]} {right[i]}")

n = int(input())
arr = [int(x) for x in input().split(' ')]
l=-1
r=-1
for i in range(n):
    if i==0:
        l=-1;
        for j in range(i+1,n):
            if arr[j]<arr[i]:
                r=j
                print(l,r)
                break
        if(r==-1):
            print(l,r)
    if i==n-1:
        r=-1
        for j in range(n-2,-1,-1):
            if arr[j]<arr[i]:
                l=j
                print(l,r)
                break
        if(l==-1):
            print(l,r)
    if 0<i<n-1:
        for j in range(i-1,-1,-1):
            if arr[j]<arr[i]:
                l=j
                break
            else:
                l=-1
        for j in range(i+1,n):
            if arr[j]<arr[i]:
                r=j
                break
            else:
                r=-1
        print(l,r)

n = int(input())
arr = list(map(int,input().strip().split(' ')))
L=[-1 for i in range(n)]
R=[-1 for i in range(n)]
min_t=[]
for i in range(n):
    while len(min_t)>0 and arr[min_t[-1]] >= arr[i]:
        min_t.pop()
    if len(min_t) != 0:
        L[i]=min_t[-1]
    min_t.append(i)
min_t=[]
for i in range(n-1,-1,-1):
    while len(min_t)>0 and arr[min_t[-1]] >= arr[i]:
        min_t.pop()
    if len(min_t) != 0:
        R[i]=min_t[-1]
    min_t.append(i)
for i in range(n):
    print(L[i],R[i])