package dopolnitelni_casovi.linkedlists;

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

/**
 * ----------------------------
 * Project: APS
 * Package: dopolnitelni_casovi.linkedlists
 * Created on: 29.5.2016, 14:07
 * 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 PodeliSporedProsek {
    /* TODO:
    Дадена е еднострано поврзана листа чии што јазли содржат по еден природен број.
Листата треба да се подели на две резултантни листи, т.ш. во првата листа треба да се сместат сите јазли
 кои содржат броеви помали или еднакви на просекот на листата (просек на листа претставува математички просек
 од сите природни броеви кои се јавуваат во листата), а во втората сите јазли кои содржат броеви поголеми од
 просекот на листата. Јазлите во резултантните листи се додаваат според редоследот по кој се појавуваат во дадената
  листа.

Во првиот ред од влезот е даден бројот на јазли во листата, а во вториот ред се дадени броевите од кои се
 составени јазлите по редослед во листата. Во првиот ред од излезот треба да се испечатат јазлите по редослед
 од првата резултантна листа (броеви помали или еднакви на просекот на листата), во вториот ред од втората
 (броеви поголеми од просекот на листата) .
     */
    /*
    * Sample input
5
4 2 1 5 3
Sample output
2 1 3
4 5
    * */
    public static void main(String[] args) {
        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));
            }
            int prosek = najdiProsek(lista);
            List<Integer> pomaliEdnakvi = pomaliEdnakviProsek(lista, prosek);
            List<Integer> pogolemiProsek = pogolemiProsek(lista, prosek);
            for (Integer i : pomaliEdnakvi) {
                System.out.print(i + " ");
            }
            System.out.println();
            for (Integer i : pogolemiProsek) {
                System.out.print(i + " ");
            }

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

    static List<Integer> pomaliEdnakviProsek(List<Integer> lista, int prosek) {
        List<Integer> rezultat = new ArrayList<>();
        for (Integer i : lista) {
            if (i <= prosek) {
                rezultat.add(i);
            }
        }
        return rezultat;
    }

    static List<Integer> pogolemiProsek(List<Integer> lista, int prosek) {
        List<Integer> rezultat = new ArrayList<>();
        for (Integer i : lista) {
            if (i > prosek) {
                rezultat.add(i);
            }
        }
        return rezultat;
    }

    static int najdiProsek(List<Integer> lista) {
        int prosek = 0;
        int suma = 0;
        for (Integer i : lista) {
            suma += i;
        }
        prosek = suma / lista.size();
        return prosek;
    }

}