#include<iostream>
#define _debug_ 1
using namespace std;
int *b;
int MAX;
long counter;
void print(int queue );
void search(int stack , int queue ,int d );
int main()
{
int stack=0;
int queue;
if(_debug_)counter=0;
cin>>MAX;
if(MAX<=0)exit(0);
b=new int[MAX];
queue=MAX-1;
search(stack,queue, 1);
delete []b;
return 0;
}
void print(int queue )
{
int i;
for(i=0;i<MAX;i++)
cout<<b[i]<<" -> ";
if(_debug_)
cout<<endl<<counter++<<endl;
else cout<<endl;
}
void search( int stack ,int queue ,int d)
{
if(stack==queue){
b[stack]=d;
print(queue);
}else{
b[stack]=d;
stack++;
search(stack,queue,d+1);
stack--;
b[queue]=d;
queue--;
search(stack,queue,d+1);
}
}
