题解 | #火车进站#只有一条进出站的路，所以后面的火车不能在前面的火车没有入站之前就入站

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static ArrayList<List<Integer>> res = new ArrayList<>();//结果集
    public static List<Integer> path = new ArrayList<>();//单次结果
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int[] arr = new int[n];
            for(int i=0;i<n;i++){
                arr[i] = in.nextInt();
            }
            dfs(arr,n,new Stack<Integer>(),0,0);
            ArrayList<String> ans = new ArrayList<>();//收集结果,将List<String>转化为String
            StringBuilder sb = new StringBuilder();
            for(List<Integer> l : res){
                sb = new StringBuilder();//清空
                for(int i=0;i<n;i++){
                    sb.append(l.get(i));
                    if(i!=n-1){
                        sb.append(" ");
                    }
                }
                ans.add(sb.toString());
            }
            Collections.sort(ans);//默认升序排列
            for(String s:ans){
                System.out.println(s);
            }
        }
    }
    public static void dfs(int[] arr,int n,Stack<Integer> stack,int in,int out){
        //终止条件，火车全部入站，又出站了
        if(in == n && out == n){
            res.add(new ArrayList<>(path));
            return;
        }
        if(in != n){
            stack.push(arr[in]);//进站
            dfs(arr,n,stack,in+1,out);
            stack.pop();//回溯
        }
        if(!stack.isEmpty()){//站内不是空的就可以选择出站
            int x = stack.pop(); 
            path.add(x);
            dfs(arr,n,stack,in,out+1);
            path.remove(path.size()-1);//回溯
            stack.push(x);//恢复现场
        }
    }
}