思路：对火车有三种状态：已出栈，仍在栈中，未入栈，对这三种状态，由于入栈顺序固定为从小到大，因此dfs递归遍历先遍历到的出栈顺序必然是字典序更小的顺序，则直接对这三种状态dfs即可

#include<iostream>
#include<vector>
#include<algorithm>
#include<stack>

using namespace std;

vector<int> state1;//存储出栈数
stack<int> state2;//处理仍在栈中状态数
int state3=1;//state3最开始等于1
int n,cnt=20;//只输出前20种

void dfs()
{
    if(!cnt)return;
    if(state1.size()==n){
        cnt--;
        for(auto it:state1)cout<<it;
        cout<<endl;
        return;//每遇到一种方案打印一次，此时先打印的必然是按字典序更小的
    }
    if(state2.size()){
        state1.push_back(state2.top());
        state2.pop();
        dfs();
        state2.push(state1.back());//记得恢复现场
        state1.pop_back();
    }
    if(state3<=n){
        state2.push(state3);
        state3++;
        dfs();
        state2.pop();
        state3--;
    }
}

int main()
{
    cin>>n;
    dfs();
    return 0;
}