package dopolnitelni_casovi.linkedlists;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

/**
 * ----------------------------
 * Project: APS
 * Package: dopolnitelni_casovi.linkedlists
 * Created on: 29.5.2016, 15:06
 * IDE: IntelliJ IDEA
 * ----------------------------
 * Author: Damjan Miloshevski
 * Web: http://damjanmiloshevski.mk/
 * Phone: +389 (0)78 566 409
 * E-mail: [email protected]; [email protected]
 * Skype: damjan.milosevski
 * LinkedIn: https://mk.linkedin.com/in/damjanmiloshevski
 * GitHub: https://github.com/damsii
 * Bitbucket: https://bitbucket.org/dam_si
 */
public class PodeliSporedParnost {
    public static void main(String[] args) {
        /*
         * TODO:
         * Дадена е двострано поврзана листа чии што јазли содржат по еден природен број.
 Листата треба да се подели на две резултантни листи, т.ш. во првата резултанта листа
 ќе бидат бидат сместени јазли од влезната листа кои содржат парни броеви, а во втората – непарните.
 Јазлите во резултантните листи се додаваат наизменично почнувајќи од почетокот и крајот на влезната листа
 (т.е. прво се разгледува првиот елемент од листата и се додава во соодветната резултантна листа, па последниот,
 па вториот итн...)

Во првиот ред од влезот е даден бројот на јазли во листата, а во вториот ред се дадени броевите од кои
се составени јазлите по редослед во листата. Во првиот ред од излезот треба да се испечатат јазлите по редослед
 од првата резултантна листа (т.е. парните), во вториот ред од втората (т.е. непарните) .
          * */
        /*
        * Sample input
5
1 2 3 4 5
Sample output
2 4
1 5 3
        * */
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        List<Integer> lista = new ArrayList<>();
        try {
            int N = Integer.parseInt(in.readLine());
            String[] elementi = in.readLine().split(" ");
            for (String i : elementi) {
                lista.add(Integer.parseInt(i));
            }
            List<Integer> parni = parni(lista);
            List<Integer> neparni = neparni(lista);
            for (Integer i : parni) {
                System.out.print(i + " ");
            }
            System.out.println();
            for (Integer i : neparni) {
                System.out.print(i + " ");
            }

        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    static List<Integer> parni(List<Integer> lista) {
        List<Integer> rezultat = new ArrayList<>();
        for (Integer i : lista) {
            if (i % 2 == 0) {
                rezultat.add(i);
            }
        }
        return rezultat;
    }

    static List<Integer> neparni(List<Integer> lista) {
        List<Integer> rezultat = new ArrayList<>();
        for (Integer i : lista) {
            if (i % 2 != 0) {
                rezultat.add(i);
            }
        }
        return rezultat;
    }
}