import java.util.Arrays;
import java.util.Scanner;
import java.util.Random;

public class main {
	static double[] A; // The array to be sorted
	static double[] B; // A copy of A, to sort with the quadratic sorting algorithm

	static void generateData(double[] A) {// Fills array A[] with random values.
		Random r = new Random();
		for (int i = 0; i < A.length; i++)
			A[i] = r.nextDouble();

	}

	static void heapSort(double[] Arr) { //try not to use 0 for the size of the array, it'll work, but we don't pretend like it makes sense

		//Initialize heap
		for(int i=0;i<Arr.length;i++){
			double numberToAdd = Arr[i]; //this is the number we wish to insert into the heap
			if(i==0){
				Arr[0]=numberToAdd;
			}else{
				int currentParentIndex= (int) (Math.ceil((double)i/2)-1);
				int currentChildIndex=i;
				while(currentChildIndex!=0 && numberToAdd<Arr[currentParentIndex] ){
					Arr[currentChildIndex]=Arr[currentParentIndex];
					currentChildIndex=currentParentIndex;
					currentParentIndex=(int)((double)currentParentIndex/2);	
				}
				Arr[currentChildIndex]=numberToAdd;
			}
		}

		
		for(int j=Arr.length-1;j>0;j--){
			double holdingBackValue=Arr[j]; //store the last value in the heap array
			Arr[j]=Arr[0]; //set the first element in the sorted array equal to the next min 
			Arr[0]=holdingBackValue; //Now we need to percolate down
			int i=0;
			while(2*i+1<j){//make sure at least the left child is still in the heap array
				int m=2*i+1; //assume the left child is minimum 
				if((2*i+2)<j && Arr[2*i+2]<Arr[2*i+1]){ //if right child in heap array and less than left child 
					m=2*i+2; // say the minimum child is the right child 
				}
				if(Arr[m]>=Arr[i]){break;}//if we don't have it that the minimum child value is less than the value at the parent, we exit the loop and know that the value is in its rightful place
				double tmp = Arr[m]; //otherwise we swap the two
				Arr[m] = Arr[i];
				Arr[i]=tmp;
				i=m; //and call that child the new parent, and start all over
			}
		}
		
		for(int j=0;j<Arr.length/2;j++){ 
	    	double temp=Arr[Arr.length-j-1];
	    	Arr[Arr.length-j-1]=Arr[j];
	    	Arr[j]=temp;
	    }	
	
	}


	static void quadSort(double[] Arr) { //try not to use 0 for the size of the array, it'll work, but we don't pretend like it makes sense
		//insertion sort

		int i;

		for(int p=1;p<Arr.length;p++){
			double valueToInsert=Arr[p];
			for(i=p;i>0&&valueToInsert<Arr[i-1];i--){
				Arr[i]=Arr[i-1];
			}
			Arr[i]=valueToInsert;

		}


	}



	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		int N = in.nextInt();


		A = new double[N];
		generateData(A);

		for(int i=0;i<3;i++){
			if(i==0){
				System.out.println("Random Input");
			}else if(i==1){
				Arrays.sort(A);
				System.out.println("Sorted Input");
				//System.out.println(Arrays.toString(A));
			}else if(i==2){
				Arrays.sort(A);
			    for(int j=0;j<A.length/2;j++){
			    	double temp=A[A.length-j-1];
			    	A[A.length-j-1]=A[j];
			    	A[j]=temp;
			    }			    
				System.out.println("Reverse Sorted Input");
				//System.out.println(Arrays.toString(A));
			}
			B = A.clone();
			long time1 = System.nanoTime();// Records the current time (in nano-seconds)							
			heapSort(A);
			long time2 = System.nanoTime();
			quadSort(B);
			long time3 = System.nanoTime();
			System.out.printf("Heapsort took %6d ms while quadSort took %6d ms\n",
					(time2 - time1) / 1000, (time3 - time2) / 1000);
		}
	}
}