﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            Red lista = new Red();
            SortiraniRed listaSort = new SortiraniRed();
            int n = Convert.ToInt32(Console.ReadLine());
            for (int i = 0; i < n; i++)
            {
                int x = Convert.ToInt32(Console.ReadLine());
                lista.dodajNovog(x);
                listaSort.dodajNovog(x);
            }
            lista.stampaj();
            listaSort.stampaj();
            //int k = Convert.ToInt32(Console.ReadLine());
            //lista.izbaci(k);


            Console.ReadKey();
        }
    }

    public class ClanListe
    {
        public int vrednost;
        public ClanListe sledeci;

        public ClanListe(int x)
        {
            vrednost = x;
            sledeci = null;
        }
    }
    public class Red
    {
        protected ClanListe pocetak=null;
        public void dodajNovog(int i)
        {
            ClanListe nov = new ClanListe(i);
            if (pocetak == null)
            {
                pocetak = nov;
            }
            else
            {
                ClanListe tekuci = pocetak;
                while (tekuci.sledeci != null)
                    tekuci = tekuci.sledeci;
                tekuci.sledeci = nov;
            }
        }

        public void izbaci(int i)
        {
            while(pocetak!=null&&pocetak.vrednost==i)
            {
                pocetak = pocetak.sledeci;
            }
            if (pocetak == null)
                return;
            ClanListe tekuci = pocetak;
            while (tekuci.sledeci != null)
            {
                if(tekuci.sledeci.vrednost==i)
                {
                    tekuci.sledeci = tekuci.sledeci.sledeci;
                    stampaj();
                }
                else
                {
                    tekuci = tekuci.sledeci;
                }
            }
            
            
        }

        public void stampaj()
        {
            ClanListe tekuci = pocetak;
            while (tekuci.sledeci != null)
            {
                Console.Write(tekuci.vrednost+" ");
                tekuci = tekuci.sledeci;
            }
            Console.Write(tekuci.vrednost);
            Console.WriteLine();
        }
    }

    public class SortiraniRed : Red
    {
        public void dodajNovog(int i)
        {
            ClanListe nov = new ClanListe(i);
            if (pocetak == null)
            {
                pocetak = nov;
                return;
            }
            if(i<pocetak.vrednost)
            {
                nov.sledeci = pocetak;
                pocetak = nov;
                return;
            }
            ClanListe tekuci = pocetak;
            while (tekuci.sledeci != null && 
                tekuci.sledeci.vrednost < nov.vrednost)
            {
                tekuci = tekuci.sledeci;
            }
            if (tekuci.sledeci == null)
                tekuci.sledeci = nov;
            else
            {
                nov.sledeci = tekuci.sledeci;
                tekuci.sledeci = nov;
            }
        }
    }
}
