Egy raktárban egyetlen hosszú sorban ládák vannak. Minden láda kocka alakú, de méretük különböző lehet. A ládák egymásra rakásával akarnak helyet felszabadítani. A biztonsági előírás szerint több ládát is lehet egymásra rakni, de minden ládát csak nálánál nagyobbra lehet helyezni. Továbbá, az i-edik helyen lévő ládát csak akkor lehet rárakni a j-edik helyen lévő torony tetejére, ha az i-edik és j-edik helyek között már nincs láda (j lehet akár kisebb, akár nagyobb, mint i). Minden ládát legfeljebb egyszer lehet mozgatni. Készíts programot (pakol.pas, …), amely kiszámítja, hogy legkevesebb hány toronyba lehet a ládákat összepakolni!

A pakol.be szöveges állomány első sorában a ládák N (2N30000) száma van. A má-sodik sor pontosan N pozitív egész számot tartalmaz egy-egy szóközzel elválasztva, a ládák méreteit. A második sorban lévő számok mindegyike 1 és 30000 közötti érték.

A pakol.ki szöveges állomány első és egyetlen sora egy egész számot tartalmazzon, azt a legkisebb M számot, hogy a bementben megadott ládasor összepakolható M számú toronyba!

Példa:

pakol.be

10
1 2 4 6 7 5 3 2 5 3

pakol.ki

2

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
 
namespace pakol
{
    class Program
    {
        static int[] dobozMeretek;
        static int dobozDb;
        static StreamWriter ki;
 
        static void beolvasas()
        {
            StreamReader be = new StreamReader("pakol.be");
            dobozDb = Convert.ToInt32(be.ReadLine());
            dobozMeretek = new int[dobozDb];
            string[] mezok = be.ReadLine().Split(' ');
            for (int i = 0; i < dobozDb; i++)
            {
                dobozMeretek[i] = Convert.ToInt32(mezok[i]);
            }
            be.Close();
            // Kiiratás
            for (int i = 0; i < dobozDb; i++)
            {
                Console.Write(dobozMeretek[i]+" ");
            }
            Console.WriteLine();
        }
 
        static int elsoLokalisMax(int[] tomb, int kezdoIndex)
        {
            int i = kezdoIndex;
            while (i < dobozDb - 1 && tomb[i] < tomb[i + 1]) i++;
            return i;
        }
 
        static void tornyoz()
        {
            int db = 0;
            int kezdoIndex = 0;
            while (kezdoIndex < dobozDb) {
                int maxIndex = elsoLokalisMax(dobozMeretek, kezdoIndex);
                int bal = maxIndex - 1;
                int jobb = maxIndex + 1;
                int toronytetoMeret = dobozMeretek[maxIndex];
                while (
                    bal >= kezdoIndex
                    || (
                        jobb < dobozDb
                        && toronytetoMeret > dobozMeretek[jobb]
                    )
                )
                {
                    Console.WriteLine(toronytetoMeret);
                    if (bal >= kezdoIndex
                        && (
                            jobb >= dobozDb
                            || dobozMeretek[jobb] >= toronytetoMeret
                            || dobozMeretek[bal] >= dobozMeretek[jobb])
                        )
                    {
                        toronytetoMeret = dobozMeretek[bal];
                        bal--;
                    }
                    else
                    {
                        toronytetoMeret = dobozMeretek[jobb];
                        jobb++;
                    }
                    Console.WriteLine("{0} {1}", bal, jobb);
                }
                Console.WriteLine("Max: {0} bal: {1} jobb: {2}", maxIndex, bal, jobb);
                kezdoIndex = jobb;
                db++;
            }
            Console.WriteLine("Tornyok száma: {0}", db);
            ki.WriteLine(db);
        }
 
        static void Main(string[] args)
        {
            beolvasas();
            ki = new StreamWriter("pakol.ki");
            tornyoz();
            ki.Close();
            Console.ReadKey();
        }
    }
}