#include <iostream>
#include <algorithm>
using namespace std;
struct Node{
int data;
int index;
Node* left;
Node* right;
Node* parent;
};
bool cmpNode(const Node &x,const Node &y){
return x.data < y.data;
}
void pre_order(Node* ptr){
cout<< ptr->data <<' ';
if(ptr->left)
pre_order(ptr->left);
if(ptr->right)
pre_order(ptr->right);
}
int main(){
int N;
Node* nodes=NULL;
Node* ptr=NULL;
while(cin>>N){
nodes=new Node[N];
for(int i=0;i<N;++i){
cin>>nodes[i].data;
nodes[i].index=i;
nodes[i].left=NULL;
nodes[i].right=NULL;
nodes[i].parent=NULL;
}
sort(nodes,nodes+N,cmpNode);
for(int i=1;i<N;++i){
if(nodes[i].index<nodes[i-1].index){
if(nodes[i-1].parent){
ptr=nodes[i-1].parent;
bool done=false;
while(ptr!=NULL){
if(nodes[i].index < ptr->index){
if(ptr->parent)
ptr=ptr->parent;
else break;
}
else{
nodes[i].parent=ptr;
nodes[i].left=ptr->right;
ptr->right->parent=&nodes[i];
ptr->right=&nodes[i];
done=true;
break;
}
}
if(!done){
nodes[i].left=ptr;
ptr->parent=&nodes[i];
}
}
else{
nodes[i].left=&nodes[i-1];
nodes[i-1].parent=&nodes[i];
}
}
else{
nodes[i-1].right=&nodes[i];
nodes[i].parent=&nodes[i-1];
}
}
ptr=&nodes[0];
while(ptr->parent!=NULL)
ptr=ptr->parent;
pre_order(ptr);
cout<<endl;
delete[] nodes;
nodes=NULL;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RydWN0IE5vZGV7CglpbnQgZGF0YTsKCWludCBpbmRleDsKCU5vZGUqIGxlZnQ7CglOb2RlKiByaWdodDsKCU5vZGUqIHBhcmVudDsKfTsKYm9vbCBjbXBOb2RlKGNvbnN0IE5vZGUgJngsY29uc3QgTm9kZSAmeSl7CglyZXR1cm4geC5kYXRhIDwgeS5kYXRhOwp9CnZvaWQgcHJlX29yZGVyKE5vZGUqIHB0cil7Cgljb3V0PDwgcHRyLT5kYXRhIDw8JyAnOwoJaWYocHRyLT5sZWZ0KQoJCXByZV9vcmRlcihwdHItPmxlZnQpOwoJaWYocHRyLT5yaWdodCkKCQlwcmVfb3JkZXIocHRyLT5yaWdodCk7Cn0KaW50IG1haW4oKXsKCWludCBOOwoJTm9kZSogbm9kZXM9TlVMTDsKCU5vZGUqIHB0cj1OVUxMOwoJd2hpbGUoY2luPj5OKXsKCQlub2Rlcz1uZXcgTm9kZVtOXTsKCQlmb3IoaW50IGk9MDtpPE47KytpKXsKCQkJY2luPj5ub2Rlc1tpXS5kYXRhOwoJCQlub2Rlc1tpXS5pbmRleD1pOwoJCQlub2Rlc1tpXS5sZWZ0PU5VTEw7CgkJCW5vZGVzW2ldLnJpZ2h0PU5VTEw7CgkJCW5vZGVzW2ldLnBhcmVudD1OVUxMOwoJCX0KCQlzb3J0KG5vZGVzLG5vZGVzK04sY21wTm9kZSk7CiAgICAgICAgZm9yKGludCBpPTE7aTxOOysraSl7CiAgICAgICAgICAgIGlmKG5vZGVzW2ldLmluZGV4PG5vZGVzW2ktMV0uaW5kZXgpewogICAgICAgICAgICAgICAgaWYobm9kZXNbaS0xXS5wYXJlbnQpewogICAgICAgICAgICAgICAgICAgIHB0cj1ub2Rlc1tpLTFdLnBhcmVudDsKICAgICAgICAgICAgICAgICAgICBib29sIGRvbmU9ZmFsc2U7CiAgICAgICAgICAgICAgICAgICAgd2hpbGUocHRyIT1OVUxMKXsKICAgICAgICAgICAgICAgICAgICAgICAgaWYobm9kZXNbaV0uaW5kZXggPCBwdHItPmluZGV4KXsKCQkJCQkJCWlmKHB0ci0+cGFyZW50KQoJCQkJCQkJCXB0cj1wdHItPnBhcmVudDsKCQkJCQkJCWVsc2UgYnJlYWs7CgkJCQkJCX0KICAgICAgICAgICAgICAgICAgICAgICAgZWxzZXsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG5vZGVzW2ldLnBhcmVudD1wdHI7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBub2Rlc1tpXS5sZWZ0PXB0ci0+cmlnaHQ7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBwdHItPnJpZ2h0LT5wYXJlbnQ9Jm5vZGVzW2ldOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgcHRyLT5yaWdodD0mbm9kZXNbaV07CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBkb25lPXRydWU7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICBpZighZG9uZSl7CiAgICAgICAgICAgICAgICAgICAgICAgIG5vZGVzW2ldLmxlZnQ9cHRyOwogICAgICAgICAgICAgICAgICAgICAgICBwdHItPnBhcmVudD0mbm9kZXNbaV07CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZXsKICAgICAgICAgICAgICAgICAgICBub2Rlc1tpXS5sZWZ0PSZub2Rlc1tpLTFdOwogICAgICAgICAgICAgICAgICAgIG5vZGVzW2ktMV0ucGFyZW50PSZub2Rlc1tpXTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlewoJCQkJbm9kZXNbaS0xXS5yaWdodD0mbm9kZXNbaV07CiAgICAgICAgICAgICAgICBub2Rlc1tpXS5wYXJlbnQ9Jm5vZGVzW2ktMV07CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcHRyPSZub2Rlc1swXTsKICAgICAgICB3aGlsZShwdHItPnBhcmVudCE9TlVMTCkKICAgICAgICAgICAgcHRyPXB0ci0+cGFyZW50OwogICAgICAgIHByZV9vcmRlcihwdHIpOwoJCWNvdXQ8PGVuZGw7CgkJZGVsZXRlW10gbm9kZXM7CgkJbm9kZXM9TlVMTDsKCX0KCXJldHVybiAwOwp9