import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Random;

public class Ld1161RDB092 {

	public static void quickSort(int[] a,int l,int r){
		int i=l, j=r, m=a[l+(r-l)/2];
		do{
		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--;
		}
		}while (i<=j);
		if (j>l)
		quickSort(a,l,j);
		if (r>i)
		quickSort(a,i,r);
		}

		public static void randomNum(int[] a){
		Random rnd = new Random();
		for(int i=0;i<a.length;i++)
		a[i] =rnd.nextInt(1000)+50;
		}
		// Random numbers generator


		public static void decreaseNum(int[] a) {
		Random rnd =new Random();
		int b = rnd.nextInt(1000);
		for(int i=0;i<a.length;i++)
		a[i]=b--;
		}
		// decreaseNum(A);


		public static void increaseNum(int[] a){
		Random rnd = new Random();
		int b = rnd.nextInt(100);
		for (int i=0;i<a.length;i++)
		a[i]=b++;
		a[7]=35;a[17]=78;
		}
		// increaseNum(A);


		public static void firstMethod(int[] a){
		int i; boolean b = true;
		while (b=true){
			b=false;
		for (i=0; i<a.length;i=i+2) {
			if (a[i]>a[i+1]);
				a[i]=a[i+1];
						a[i+1]=a[i];
						b=true;
			}
		}
		for (i=1; i<a.length;i=i+2) {
			if (a[i]>a[i+1]);
				a[i]=a[i+1];
				a[i+1]=a[i];
				b=true;
			}
		}



		public static void secondMethod(int[] a){
		quickSort(a,0,a.length-1);
		}


		public static void main(String[] args) throws Exception {
		System.out.println("Lauris Ungurs RDBI01 161RDB092");
		String s;int x,n,i;
		BufferedReader reader = new BufferedReader(new
		InputStreamReader(System.in));
		try{
		System.out.println("Method:");
		s=reader.readLine();
		x=Integer.parseInt(s);
		} catch (IOException e){
		System.out.println("input-output error");
		return;}
		if (x!=1 && x!=2){
		System.out.println("input-output error");
		return;}
		try{
		System.out.println("Count:");
		s=reader.readLine();
		n=Integer.parseInt(s);
		} catch (Exception e){
		System.out.println("input-output error");
		return;
		}
		int A[] = new int[n];
		System.out.println("Items:");
		for(i=0;i<n;i++){
		try{
		s=reader.readLine();
		A[i]=Integer.parseInt(s);
		} catch (Exception e){
		System.out.println("input-output error");
		return;}
		}
		// long t1 = System.nanoTime();
		if (x==1){
		firstMethod(A);
		}
		else {
		secondMethod(A);
		}
		// long t2 = System.nanoTime();
		// long t = t2-t1;
		// System.out.println("Time:");
		// System.out.println("t=" + t);
		System.out.println("Sorted:");
		for (i=0;i<n;i++)
		System.out.print(A[i] + " ");
		}}