#include<fstream>
#include<time.h>
#define maxn 500010
using namespace std;
int n,left,right;
int arr[maxn];
ifstream f("algsort.in");
ofstream g("algsort.out");

void citire(){
	f>>n;
	for(int i=1;i<=n;i++)
		f>>arr[i];
}

void quickSort(int arr[], int left, int right) {
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];
      /* partition */
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };
      /* recursion */
      if (left < j)
            quickSort(arr, left, j);
      if (i < right)
            quickSort(arr, i, right);
}

int main(){
	citire();
	    clock_t t1,t2;
	float sec;
    t1=clock();
	
	quickSort(arr,1,n);
	    
	t2=clock();
    float diff ((float)t2-(float)t1);
	sec=diff/CLOCKS_PER_SEC;

	for(int i=1;i<=n;i++)
		g<<arr[i]<<' ';
	g<<'\n';
	g<<sec<<'\n';
	g.close();
	return 0;
}