单调栈

单调栈即指从栈顶到栈底的元素是单增或者单减的，本题是想要查找到每个位置左右两边最近的小于它的位置，所以使用单调递减的栈。
方法是遍历整个数组的索引，若栈为空，则将该索引放入栈里，若栈不为空，则比较栈顶索引对应的值与当前遍历到的索引对应的值。
1、若栈顶索引对应的值较小，则继续将当前遍历到的索引放入栈中，保持单调减的特性
2、若栈顶索引对应的值较大，则将该索引从栈顶弹出。注意理解，此时可以找到弹出的索引对应的左右两边最近的小于它的位置，左边最近的位置--新的栈顶的索引（若栈为空，则为-1），右边最近的位置--当前遍历到的索引（若已遍历完，则为-1）

n = int(input())
arr = input().split()
arr = list(map(int,arr))

stack = []
index_list = [[] for i in range(n)]
for i in range(len(arr)):
    if not stack:
        stack.append(i)
    else:
        while stack and arr[stack[-1]] > arr[i]:
            current_index = stack.pop()
            if stack:
                index_list[current_index] = [stack[-1],i]
            else:
                index_list[current_index] = [-1,i]
        stack.append(i)

while stack:
    current_index = stack.pop()
    if stack:
        index_list[current_index] = [stack[-1],-1]
    else:
        index_list[current_index] = [-1,-1]

for i in index_list:
    print(i[0],i[1])