蓝桥杯-百亿富翁

"""
https://www.lanqiao.cn/problems/1142/learning/
"""
import os
import sys

# 请在此输入您的代码
n = int(input())
a = list(map(int, input().split()))

# 求右边第一个比其高的楼房编号
def right(a, n):
    # 单调栈
    stack = []
    # ans[i]记录右边第一座比其高的楼房编号, 如果没有默认为-1
    ans = [-1] * n
    for i, x in enumerate(a):
        while stack and x > a[stack[-1]]:
            ans[stack[-1]] = i + 1 # 楼房的编号是从1~N
            stack.pop()
        stack.append(i)
    return ans

# 求左边第一个比其高的楼房编号
def left(a ,n):
    stack = []
    ans = [-1] * n
    for i in range(n - 1, -1, -1):
        x = a[i]
        while stack and x > a[stack[-1]]:
            ans[stack[-1]] = i + 1
            stack.pop()
        stack.append(i)
    return ans

print(*left(a, n))
print(*right(a, n))