题目：

描述

给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以 数字1-9编号，火车站只有一个方向进出，同时停靠在火车站的列车中，只有后进站的出站了，先进 站的才能出站。

要求输出所有火车出站的方案，以字典序排序输出。

数据范围：1≤n≤10

进阶：时间复杂度：O(n!) ，空间复杂度：O(n)

输入描述： 第一行输入一个正整数N（0 < N <= 10），第二行包括N个正整数，范围为1到10。

输出描述： 输出以字典序从小到大排序的火车出站序列号，每个编号以空格隔开，每个输出序列换行，具体见sample。

输入：
3
1 2 3

输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1

说明： 第一种方案：1进、1出、2进、2出、3进、3出
第二种方案：1进、1出、2进、3进、3出、2出
第三种方案：1进、2进、2出、1出、3进、3出
第四种方案：1进、2进、2出、3进、3出、1出
第五种方案：1进、2进、3进、3出、2出、1出
请注意，[3,1,2]这个序列是不可能实现的。

刚看题目就不能明白为什么输入"1 2 3"不就是"3 2 1"一个答案吗？（题目中这一句：“接下来输入火车入站的序列，”直接要了俺的命了）， 输入"1 2 3", 也就是编号1、2、3这三辆火车进站了（但人家可没有说是一次来了三辆），所以呢，得猜，猜出题者到底说了什么意思。 “说明”所举例的内容就是一种提示：我（出题者）就是这么规定题目意思的。您要是没看明白，是您自己的水平问题。

据说，金圣叹记载的史上最短科举试题“二”，这个题目只有一个字，要求考生围绕这个数字展开论述，其荒诞性不言而喻。

据载，金圣叹在应试时遇到的题目“吾四十而不动心”，他在试卷上写了三十九个“动心”…

哥们那39个“动心”倒是有点理工直男的黑色幽默，不管怎么说，我总觉得他多少是在戏弄考官。哈哈。还是这位金性怪老头玩得起。

题目总归是没有错的（搞不好是打着“圣上”旗号出题的，谁敢说它错了？）而且出题范围内，题目只 有那么多，每年都要考，所以要么将其变曲折复杂，要么变含糊其辞，要么说点悄悄话…总而言之，如果揣摩不透“上意”，肯定是自己水平问题。

其实也就意味着，您不在出题者混的圈子里，而又非要去应试，是您最大的错。

啰唆多两句：
回到这道题，我仿佛看到了科举考试的鬼影在跳舞。想不到那些弯弯绕当然是自己笨…吗？

才刚git push这篇博客，就刷到“道路办何主任”的刚刚发布的为什么有人喜欢脱裤子放屁，很喜欢这哥们的文章。

代码（不给代码就是瞎哔哔个屁，但是这个年头，用最喜爱的“卡帕西”Andrej Karpathy老师的话来讲就是：编写代码即将就是tab tab tab）：

import sys

def train_out_sequences(n, trains):
    def dfs(in_index, stack, out_sequence):
        # 如果所有火车都出站，记录当前方案
        if len(out_sequence) == n:
            result.append(out_sequence[:])
            return

        # 选择入站操作
        if in_index < n:
            stack.append(trains[in_index])  # 火车入站
            dfs(in_index + 1, stack, out_sequence)  # 递归处理下一辆车
            stack.pop()  # 回溯，撤销入站操作

        # 选择出站操作
        if stack:
            out_sequence.append(stack.pop())  # 栈顶火车出站
            dfs(in_index, stack, out_sequence)  # 递归处理
            stack.append(out_sequence.pop())  # 回溯，撤销出站操作

    result = []
    dfs(0, [], [])

    # 对所有出站方案按字典序排序
    result.sort()

    return result

ins = []
for line in sys.stdin:
    a = line.strip()
    ins.append(a)

n, trains = int(ins[0]), list(map(int, ins[1].split()))
# 获取所有合法的出站方案
sequences = train_out_sequences(n, trains)

# 打印每个出站方案
for seq in sequences:
    print(" ".join(map(str, seq)))