#火车进站# | 动态规划

n = int(input())
trainnum = input().split()
def is_legal(trainlist,x,s):
    if s>= len(trainlist)-1:
        return True
    else:
        for i in range(len(trainlist)-s-1):
            if trainlist[i+s]< trainlist[i+s+1]:
                return False
    return True
dp = [ [] for _ in range(n+1) ]
dp[1].append([1])
for i in range(2,n+1):
    for s in dp[i-1]:
        for j in reversed(range(i)):
            if is_legal(s,i,j):
                dp[i].append(s[:j]+[i]+s[j:])
ans = []
for s in dp[n]:
    ans.append([trainnum[item-1] for item in s])
ans.sort()
for s in ans:
    print(' '.join(s))
        

假设进站顺序是1234567，求出所有的解，再把真实进站顺序带入再排序即可（这里我自己也没太搞懂为什么可以这样）。

先从车少的情况开始求，每多加一辆车，因为他编号最大，所以它出站之后后面的出站顺序只能按车号降序。

对所有n-1的合法出站顺序尝试在各个位置添加新车看看是否仍然合法，合法就加到n的合法出站顺序里。