#include <fstream>
using namespace std;
#define swap(a,b) ( a ^=b ^=a ^=b )

int A[500011],N;

int pozitionare(int st,int dr)
{
	int xst,xdr;
	xst=0;
	xdr=-1;
	while ( st<dr )
		if (A[st]<A[dr])
		{
			st+=xst;
			dr+=xdr;
		}
	else
	{
        swap(A[st],A[dr]);
        xst=1-xst;
        xdr=-1-xdr;
        st+=xst;
		dr+=xdr;
	}
	return st;
}

void quick(int st,int dr)
{
	int p=pozitionare(st,dr);
	if (st<p-1)
		quick(st,p-1);
	if (p+1<dr)
		quick(p+1,dr);
}

int main()
{
	ifstream F("algsort.in");
	ofstream G("algsort.out");
	
	for (int i=1;i<=N;++i)
		F>>A[i];
	quick(1,N);
	for (int i=1;i<=N;++i)
		G<<A[i];
	
	F.close();
	G.close();
	return 0;
}