#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int arr[50004],b[50004];
double t=CLOCKS_PER_SEC;
void sort(int low,int mid,int high);
void partition(int low,int high);
void insertion(int low,int high);

int main()
{
	FILE *in,*out;
	int i,j,k,l,num,n;
	in=fopen("input.txt","w");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		num=rand()%1000;
		if(num<=0)
			num=num+1000;
		fprintf(in," ");
		fprintf(in,"%d",num);

	}
	fclose(in);
	in=fopen("input.txt","r");
	i=0;
	while(fscanf(in,"%d",&num)==1)
	{
		arr[i++]=num;

	}

	clock_t t1=clock();
	partition(0,n-1);
	clock_t t2=clock();
	printf("%lf\n",(t2-t1)/t);


	fclose(in);
	out=fopen("output.txt","w");
	for(i=0;i<n;i++)
	{
		fprintf(out," %d",arr[i]);
	}
	fclose(out);


	printf("\n");
	return 0;

}

void sort(int low,int mid,int high)
{
int i,j,k,l,b[50004];
l=low;
i=low;
j=mid+1;
while((l<=mid)&&(j<=high))
  {
    if(arr[l]<=arr[j])
      {
      b[i]=arr[l];
      l++;
      }
    else
      {
      b[i]=arr[j];
      j++;
      }
    i++;
  }
if(l>mid)
  {
    for(k=j;k<=high;k++)
      {
        b[i]=arr[k];
        i++;
      }
  }
else
  {
    for(k=l;k<=mid;k++)
      {
        b[i]=arr[k];
        i++;
      }
  }
for(k=low;k<=high;k++)
    {
    arr[k]=b[k];
    }
}

void partition(int low,int high)
{
int mid;
if(high-low<15)
insertion(low,high);
else if(low<high)
  {
    mid=(low+high)/2;
    partition(low,mid);
    partition(mid+1,high);
    sort(low,mid,high);
  }
}

void insertion(int low,int high)
{
	int j,k,i;
	for(j=low+1;j<=high;j++)
	{
		k=arr[j];
		i=j-1;
		while(i>=low && arr[i]>k)
		{
			arr[i+1]=arr[i];
			i--;
		}
		arr[i+1]=k;
	}
}