Džonijs ir aizrāvies ar interesantu spēli, kuras noteikumi ir ļoti līdzīgi populārajai spēlei Tetris.

Spēle notiek uz taisnstūrveida laukuma, kura platums ir 3 kolonnas un augstums - 1000 rindu. Figūras krīt no augšas, un tās ir jāievieto tā, lai visu figūru kopējais augstums būtu pēc iespējas mazāks.

Visas figūras ir sanumurētas ar skaitļiem no 1 līdz 7:

Katru figūru, kas parādās, Džonijs var pagriezt. Pagriešanu var veikt par leņķi, kas ir 90 grādu daudzkārtnis. Pēc tam figūra krīt uz leju, līdz tā atduras pret kādu citu figūru, kas tika ievietota iepriekš, vai arī pret spēles laukuma apakšējo malu.

Džonijs var izvēlēties figūras horizontālo stāvokli, ņemot vērā, ka figūrai pilnībā jāiekļaujas spēles laukumā. Tas ir, figūru ar numuru 1 nedrīkst pagriezt (jo tās platums pārsniegtu spēles laukuma platumu), bet to drīkst ievietot jebkurā no 3 kolonnām. Ja Džonijs nolemj pagriezt figūru ar numuru 5, tad to var ievietot divos veidos - pirmajā un otrajā kolonnā vai otrajā un trešajā kolonnā.

Pēc tam kad figūra ir ievietota spēles laukumā un sāk krist, to vairs nedrīkst pagriezt vai pabīdīt. Atšķirībā no oriģinālās spēles Tetris, aizpildītās rindas netiek izmestas no spēles laukuma.

Ir dots saraksts ar figūrām, kuras secīgi jāievieto.

Uzrakstiet programmu, kas aprēķina mazāko iespējamo visu figūru augstumu pēc to ievietošanas! Citiem vārdiem sakot, atrodiet mazāko iespējamo veselo skaitli K, ka, ievietojot figūras kādā noteiktā veidā, tās visas atradīsies spēles laukuma apakšējās K rindās.

Pirmajā rindā dots vesels skaitlis N, 1 ≤ N ≤ 100, - ievietojamo figūru skaits.

Katrā no nākamajām N rindām dots kārtējās ievietojamās figūras numurs (vesels skaitlis no 1 līdz 7 ieskaitot).

Vienīgajā rindā jāizvada vesels skaitlis - mazākais iespējamais visu figūru augstums pēc to ievietošanas.

Uzdevums izmantots Horvātijas informātikas olimpiādē 2004.gadā