import java.util.Scanner;
import java.lang.System;
public class Ld_test {

	public static void firstMethod(int[] a) { //1.metode - uzlabota ieklausanas metode
		long startTime = System.nanoTime();
		int b[] = new int[2 * a.length - 1];
		int l = a.length - 1;
		int r = l;
		b[r] = a[0];

		for (int i = 1; i < a.length; i++) {
			if (b[l] >= a[i]) {
				l--;
				b[l] = a[i];
			} else if
				(b[r] <= a[i]) {
				r++;
				b[r] = a[i];
			}
			else
			{
				int j;
				for (j = l; j <= r; j++) {

					if (a[i] <= b[j])
						break;
				}
				if (j - l < r - j) {
					for (int k = l; k <= j - 1; k++)
						b[k - 1] =b[k];
						l--;
						b[j - 1] = a[i];
				}
				else
				{
					for (int k = r; k >= j; k--)
						b[k + 1] = b[k];
					r++;
					b[j] = a[i];
				}
			}
		}

		for (int i = 0; i < a.length; i++) {
			a[i] = b[l];
			l++;

		}
		long estimatedTime = System.nanoTime() - startTime;
		System.out.println("t=" + estimatedTime);

	}



		public static void secondMethod(int[] a) { //2.metode - Hoara bez rekursijas
			long startTime = System.nanoTime();
		        int left[] = new int[a.length / 2];
		        int right[] = new int[a.length / 2];

		        short p = 0;

		        int stackpos = 1;
		        int m = 0, l = 0, r = 0 ,i = 0, j = 0;

		        left[0] = 0;
		        right[0] = a.length - 1;
		        p = 3;
		        do {
		            switch (p) {

		                case 3:
		                    stackpos -= 1;
		                    l = left[stackpos];
		                    r = right[stackpos];
		                    p = 4;
		                    break;

		                case 4:
		                    m = (a[l] + a[r]) / 2;
		                    i = l;
		                    j = r;
		                    p = 6;
		                    break;

		                case 6:

		                    while (a[i] < m) i++;
		                    while (a[j] > m) j--;
		                    if (i <= j) {
		                        int temp = a[i];
		                        a[i] = a[j];
		                        a[j] = temp;
		                        i++;
		                        j--;
		                    }

		                    if (i <= j) {
		                        p = 6;
		                        break;
		                    }

		                    if (i < r) {
		                        left[stackpos] = i;
		                        right[stackpos] = r;
		                        stackpos += 1;
		                    }
		                    r = j;
		                    if (l < r) {
		                        p = 4;
		                        break;
		                    }
		                    if (stackpos > 0) {
		                        p = 3;
		                        break;
		                    } else p = 1;
		                    break;
		            }
		        } while (p != 1);
		        long estimatedTime = System.nanoTime() - startTime;
				System.out.println("t=" + estimatedTime);
				return;
		    }





	public static void main(String[] args) { //3.daļa - masīva izvade

		int numurs;

			int metode;
			System.out.println("Anete Brenčuka RDBF0 161RDB155");
			System.out.print("method: ");

			Scanner sc = new Scanner(System.in);
			if (sc.hasNextInt()){
				numurs = sc.nextInt();
			}
			else
			{
				System.out.println("input-output error");
				sc.close();
				return;
			}

	        if (numurs != 1 && numurs != 2) {
	            System.out.println("input-output error");
	            	sc.close();
	            	return;
	        }



			System.out.print("count: ");
		        if (sc.hasNextInt())
		        	metode = sc.nextInt();

		        else {
		        	System.out.println("input-output error");
		        	sc.close();
		        	return;
		        }


	        int a[] = new int[metode];

	        System.out.println("items: ");

	        for (int i = 0; i < a.length; i++) {

	        	if (sc.hasNextInt())
	        	a[i] = sc.nextInt();

	        else {
	        	System.out.println("input-output error");
	        	sc.close();
	        	return;
	        	}
	        }
	        sc.close();

			switch (numurs) {

			case 1: firstMethod(a);
			break;
			case 2: secondMethod(a);
			break;

			default:
				System.out.println("input-output error");
			return;
			}
            System.out.println("sorted: ");

            	for (int i = 0; i < a.length; i++)
            		System.out.print(a[i] + " ");
			}
		}