#include<iostream>
using namespace std;

typedef struct tagnumber
{
	int value;
	int direction;
}number; 

int conti(number[],int);
void change(number[],int);
void print(number[],int);
int max(number[],int);

void main()
{
	
	int n;
	cout<<"Enter the number: ";
	cin>>n;
	number *a = new number[n];
	for(int i=0;i<n;i++)
	{
		a[i].value=i+1;
		a[i].direction=0;
	}
	while(conti(a,n)==1)
	{
		print(a,n);
		change(a,n);
		
	}
	print(a,n);
}


int conti(number a[],int n)
{
	int k=0;
	for (int i=1;i<n-1;i++)
	{
	
		if(a[i].direction==0)
		{
			
				if(a[i-1].value<a[i].value)
					k=1;
			
		}
		if (a[i].direction==1)
		{
			if (a[i+1].value<a[i].value)
				k=1;
		}
		if(a[n-1].direction==0)
		{
			if (a[n-2].value<a[n-1].value)
				k=1;
		}
		if(a[0].direction==1)
		{
			if(a[1].value<a[0].value)
				k=1;
		}
		
	}
	return k;
}

void change(number a[],int n)
{
	int m=max(a,n);
	if(a[m].direction==0)
	{
		int temp1,temp2;
		temp1=a[m-1].direction;
		temp2=a[m-1].value;
		a[m-1].direction=a[m].direction;
		a[m-1].value=a[m].value;
		a[m].direction=temp1;
		a[m].value=temp2;
	}
	else if(a[m].direction==1)
	{
		int temp3,temp4;
		temp3=a[m+1].direction;
		temp4=a[m+1].value;
		a[m+1].direction=a[m].direction;
		a[m+1].value=a[m].value;
		a[m].direction=temp3;
		a[m].value=temp4;
	}
}

		
int max(number a[],int n)
{

	int k=0;
	int m=a[0].value;
	for(int t=1;t<n;t++)
	{
		if (a[t].value>m)
		{
			m=a[t].value;
			k=t;
		}
	}
	if((k==0&&(a[k].direction==0))||(k==n-1&&(a[k].direction==1)))
	{
		
		if(a[k].direction==0)
			a[k].direction=1;
		else
			a[k].direction=0;
	    int p=0;
		for(int i=1;i<n-1&&p==0;i++)
		{
			
			for(int j=0;j<n;j++)
			{
				int q=0;
			  for(int j1=0;j1<n;j1++)
			  {
				if(a[j1].value>a[j].value)
					q++;
			  }
			
			  if(q==i)
			  {
				k=j;
				if((k==0&&a[k].direction==0)||(k==n-1&&a[k].direction==1))
				{
						if(a[k].direction==0)
			                a[k].direction=1;
		                else
			                a[k].direction=0;
				}
				else
				{
					if(k!=0&&k!=n-1)
					{
						if((a[k].direction==0&&(a[k].value<a[k-1].value))||(a[k].direction==1&&(a[k].value<a[k+1].value)))
						{
							if(a[k].direction==0)
			                   a[k].direction=1;
		                    else
			                   a[k].direction=0;
						}
						else
						
							p=1;
						

					
					}
					else
						p=1;
				}
			}
		}
		}
	}
	
	return k;
}


void print(number a[],int n)
{
	for(int i=0;i<n;i++)
	{
		cout<<a[i].value<<' ';
	}
	cout<<endl;
}