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

class Tema08{

    public static void separate(int[] arr) {
        int evenN = 0;
        int oddN = 0;

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] % 2 == 0) {
                evenN++;
            } else {
                oddN++;
            }
        }

        int evens[] = new int[evenN];
        int odds[] = new int[oddN];

        int k = 0;
        int j = 0;

        for (int i = 0; i < arr.length ; i++) {
            if (arr[i] % 2 == 0) {
                evens[k++] = arr[i];
            }else{
                odds[j++] = arr[i];
            }
        }
        System.out.println("Sorted evens:");
        System.out.println(Arrays.toString(evens));

        System.out.println("Sorted odds:");
        System.out.println(Arrays.toString(odds));
    }


        public static void evens ( int[] evenN){
            int BUFF, k;
            boolean swap;

            do {
                swap = false;
                for (k = 0; k < evenN.length - 1; k++) {
                    if (evenN[k] > evenN[k + 1]) {
                        swap = true;
                        BUFF = evenN[k];
                        evenN[k] = evenN[k + 1];
                        evenN[k + 1] = BUFF;
                    }
                }
            } while (swap);
        }


        public static void odds ( int[] oddN){
            int FirstUnsortedElement;
            int LastSortedElement;


            for (int i = 1; i < oddN.length; i++) {
                FirstUnsortedElement = oddN[i];
                LastSortedElement = i - 1;

                while (LastSortedElement >= 0 && oddN[LastSortedElement] < FirstUnsortedElement) {
                    oddN[LastSortedElement + 1] = oddN[LastSortedElement];
                    LastSortedElement = LastSortedElement - 1;
                }
                oddN[LastSortedElement + 1] = FirstUnsortedElement;
            }
        }

       public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        System.out.println("Input number of elements: ");
        int n = scan.nextInt();

        int [] arr = new int[n];

        for (int i = 0; i < n; i++) {
            System.out.printf("Input [%d] element: ", i);
            arr[i] = scan.nextInt();
        }

        System.out.println("Before sorting:");
        System.out.println(Arrays.toString(arr));

        separate(arr);
        evens(arr);
        odds(arr);

        scan.close();
    }
}