using System;
using System.Collections.Generic;

class ExoListe
{
    static void Main()
    {
        List<int> f = new List<int>() { 1, 2, 9, 11, 14 };
        Random r = new Random();


        List<int> fe = new List<int>() { 3, 5, 8, 12 };


        // List<int> fer = new List<int>() { 1, 2, 4, 2, 99, 9, 8, 7, 2, 7, 6 };


        // interclassementDeuxListeTrie(fe, f);
        // TriParInsertion(fer);

        List<int> fer = new List<int>() { 503, 087, 512, 061, 908, 170, 897, 275, 653, 426, 154, 509, 612, 677, 765, 703 };
        TriParFusion(fer);
        // interclassementDeuxListeTrie(f, fe);


    }
    public static List<int> fibonacci(int n)
    {
        List<int> fibonacci = new List<int>();
        fibonacci.Add(1);
        fibonacci.Add(1);
        for (int i = 2; i < n; i++)
        {
            fibonacci.Add(fibonacci[i - 1] + fibonacci[i - 2]);
        }
        return fibonacci;
    }
    public static void show(List<int> li)
    {
        foreach (int nbr in li)
        {
            Console.Write(nbr + " ,");
        }
        Console.WriteLine();
    }

    public static int occ(List<int> li, int x)
    {
        int occu = 0;
        for (int i = 0; i < li.Count; i++)
        {
            if (x == li[i])
            {
                occu++;
            }
        }
        return occu;

    }

    public static int firstAppa(List<int> li, int x)
    {
        int index = -1;
        int i = 0;
        while (i < li.Count && index == -1)
        {
            if (li[i] == x)
            {
                index = i;
            }
        }
        return index;
    }
    public static int firstAppaTrie(List<int> li, int x)
    {
        int index = -1;
        int i = 0;
        while (i < li.Count && index == -1 && li[i] <= x)
        {
            if (li[i] == x)
            {
                index = i;
            }
            i++;
        }
        return index;
    }

    public static int max(List<int> li)
    {
        int maxI = 0;
        for (int i = 1; i < li.Count; i++)
        {
            if (li[i] > li[maxI])
            {
                maxI = i;
            }
        }
        return li[maxI];
    }

    public static int min(List<int> li, int borneInf, int borneSup)
    {
        int minI = borneInf;
        for (int i = borneInf + 1; i <= borneSup; i++)
        {
            if (li[i] < li[minI])
            {
                minI = i;
            }
        }
        return li[minI];
    }

    public static bool estTrie(List<int> li)
    {
        bool estTrie = true;
        int i = 1;
        while (i < li.Count && estTrie)
        {
            if (li[i - 1].CompareTo(li[i]) > 0)
            {
                estTrie = false;
            }
            i++;
        }
        return estTrie;
    }
    public static bool estTrieSousListe(List<int> li, int borneInf, int borneSup)
    {
        bool estTrie = true;
        int i = borneInf + 1;
        while (i <= borneSup && estTrie)
        {
            if (li[i - 1].CompareTo(li[i]) > 0)
            {
                estTrie = false;
            }
            i++;
        }
        return estTrie;
    }

    /* /
    public static int rangValSup(List<int> li, int x) {
        int index = -1;
        int i = 0;
        while (i < li.Count && index == -1) {
            if (li[i] > x) {
                index=i;
            }
        }
        return index;
    } */
    public static List<int> TriParInsertion(List<int> li)
    {
        // Version à moi
        // List<int> liTrie = new List<int>();
        // liTrie.Add(li[0]);
        // for (int i = 1; i < li.Count; i++)
        // {
        //     int rangValSup = -1;
        //     for (int j = 0; j < liTrie.Count && rangValSup == -1; j++)
        //     {
        //         if (liTrie[j] > li[i])
        //         {
        //             rangValSup = j;
        //         }
        //     }
        //     if (rangValSup == -1)
        //     { // Pas de valeur supérieur
        //         liTrie.Add(li[i]);
        //     }
        //     else
        //     {
        //         liTrie.Insert(rangValSup, li[i]);
        //     }

        //     Console.WriteLine(rangValSup);
        //     show(li);
        //     show(liTrie);
        // }
        // return liTrie;

        // Version P12.
        List<int> listTrie = new List<int>();
        listTrie.Add(li[0]);
        li.RemoveAt(0);
        while (li.Count > 0) {
            int indexValSup = -1;
            int i = 0;
            while (indexValSup == -1 && i < listTrie.Count) {
                if (listTrie[i] > li[0]) {
                    indexValSup = i;
                }
                i++;
            }

            if (indexValSup == -1) { // Pas de valeur sup.
                listTrie.Add(li[0]);
            }  else {
                listTrie.Insert(indexValSup, li[0]);
            }

            li.RemoveAt(0);
            show(li);
            show(listTrie);
            Console.WriteLine();
        }

        show(listTrie);
        return listTrie;
    }

    public static void criblePremier(List<int> li)
    {
        for (int n = li.Count - 1; n >= 0; n--)
        {
            bool estDivisible = false;
            int i = 2;
            while (i <= 9 && !estDivisible)
            {
                if (li[n] % i == 0 && i != li[n])
                {
                    estDivisible = true;
                }
                i++;
            }
            if (estDivisible)
            {
                li.Remove(n);
            }
        }
        show(li);
    }

    public static List<int> interclassementDeuxListeTrie(List<int> li1, List<int> li2)
    {
        List<int> listeTrie = new List<int>();

        while (li1.Count > 0 && li2.Count > 0)
        {
            if (li1[0] <= li2[0])
            {
                listeTrie.Add(li1[0]);
                li1.RemoveAt(0);
            }
            else
            {
                listeTrie.Add(li2[0]);
                li2.RemoveAt(0);
            }
            // show(li1);
            // show(li2);
            // show(listeTrie);
        }

        if (li1.Count > 0) {
            for (int i = 0; i < li1.Count; i++)  {
                listeTrie.Add(li1[i]);
            }
        } else if (li2.Count > 0) {
            for (int i = 0; i < li2.Count; i++)  {
                listeTrie.Add(li2[i]);
            }
        }
        return listeTrie;
    }
    public static int plusGrandeMonotonie(List<int> li)
    {
        List<int> monotonie = new List<int>();
        int longueurMaxMonotonie = 1;
        int longueurMonotonieActuelle = 1;
        int indexStartMonotonie = 0;
        for (int i = 1; i < li.Count; i++)
        {

            if (li[i] > li[i - 1])
            {
                longueurMonotonieActuelle++;
            }

            // Si non n < n+1 et que la longueur de la dernière monotonie est maximale:
            else if (longueurMonotonieActuelle > longueurMaxMonotonie)
            {

                longueurMaxMonotonie = longueurMonotonieActuelle;
                // Rappel: On est au i tel que li[i] < li[i-1] (début de la monotonie suivante.)
                // Pour ne pas avoir la ligne suivante, on pourrait aussi créer 2 variables "index" ici.
                indexStartMonotonie = i - longueurMaxMonotonie;
                longueurMonotonieActuelle = 1;
            }
        }

        // On reconstruit une liste = plus grande monotonie croissante
        for (int i = indexStartMonotonie; i < longueurMaxMonotonie + indexStartMonotonie; i++)
        {
            monotonie.Add(li[i]);
        }
        show(li);
        show(monotonie);
        return longueurMaxMonotonie;
    }

    public static void TriParFusion(List<int> li) {
        List<int> listTrie = new List<int>();
        List<int> indexMonotonieCroissante = new List<int>();

        indexMonotonieCroissante.Add(0);
        for (int i = 1; i < li.Count; i++) {
            if (li[i-1] > li[i]) {
                indexMonotonieCroissante.Add(i);
            }
        }


        for (int i = 0; i < indexMonotonieCroissante.Count; i++) {
            int tempIndex = indexMonotonieCroissante[i];
            int tempIndexEnd = -1;
            if (i < indexMonotonieCroissante.Count-1) {
                tempIndexEnd = indexMonotonieCroissante[i+1];
            } else if (i == indexMonotonieCroissante.Count-1) {
                tempIndexEnd = li.Count;
            }

            List<int> tempListMonotonie = new List<int>();
            for (int j = tempIndex; j < tempIndexEnd; j++) {
                tempListMonotonie.Add(li[j]);
            }
            Console.Write("Monotonie traitée : ");
            show(tempListMonotonie);
            if (i == 0) {
                listTrie = tempListMonotonie;
            } else {
                listTrie = interclassementDeuxListeTrie(tempListMonotonie, listTrie);
            }
            show(listTrie);
            Console.WriteLine();
        }

    }
}