import java.util.Random;
import java.util.Scanner;
public class Ld_test {

	public static void firstMethod(int[] a) { //1.metode - uzlabota ieklausanas metode

		long t1 = 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 t2 = System.nanoTime();
		long t = t2 - t1;
		System.out.println("t="+t);
	}


		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];
	        Random randomNumberGenerator = new Random();
	        for (int i = 0; i < a.length; i++) {
	        	a[i] = randomNumberGenerator.nextInt();
	        }
	        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] + " ");
			}
}