Expert.
Put your skills to the test.

Problem summary

Wagons 1 through n arrive in this order. You may push the next arriving wagon onto a siding stack, or pop the stack into the output line. Decide whether each of five requested permutations can be produced.

Constraints

1 ≤ n ≤ 100,000.

Worked example

Official sample, transcribed with whitespace restored from the PDF.

3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

11101

Solution analysis

1. Maintain the next unused arriving wagon and the stack. Read the desired output permutation left to right. To output x, push arriving wagons until x is at the top, or no arrivals remain.
2. If x is now on top, pop it. Otherwise it is buried below another wagon, and the requested next output is impossible. Keep reading the remaining input even after detecting failure so the next permutation is parsed correctly.
3. For the requested order 3,1,2, pushing 1,2,3 and popping 3 leaves 2 above 1. The next requested wagon 1 cannot be removed, so this order contributes 0. The complete official example gives 11101.

Why it works

Before each requested output, all earlier outputs are fixed. If its wagon has not arrived, every preceding arrival must be pushed, which is forced. Once it has arrived, it can be output only if it is the stack top; pushing more wagons cannot uncover it. Thus every simulated action is necessary and every rejected step is impossible. Successful simulation explicitly realizes the permutation.

Watch out. The siding is a LIFO stack. Reset it and the arrival counter for each permutation.

An independently written complete program with standard headers.

// Key idea: Before each requested output, all earlier outputs are fixed. If its wagon has not arrived,
// every preceding arrival must be pushed, which is forced.
#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    for(int test=0;test<5;++test){
        vector<int>siding;
        int next=1;
        bool possible=true;
        for(int i=0;i<n;++i){
            int wanted;
            cin>>wanted;
            if(!possible){
                continue;
            }
            while(next<=wanted){
                siding.push_back(next++);
            }
            if(siding.empty()||siding.back()!=wanted){
                possible=false;
            }
            else{
                siding.pop_back();
            }
        }
        cout<<(possible?'1':'0');
    }
    cout<<'\n';
}