Inspektor Morse je dobio poruku koja se sastoji samo od znakova '0' (nula) i '1' (jedan). Iako mu odmah nije bilo jasno što ona predstavlja, vjeruje da je poruka zapisana tajnim kodom.

Tajni kod koristi kratke i duge signale za predstavljanje slova. Jedina slova koja se mogu pojaviti u tajnome kodu su E, T, A, N, I, M, U i D. I kratki i dugi signal se sastoje od uzastopnih jedinica ('1'). Dugi signal ima više jedinica od kratkog signala.

Npr. slovo D se tajnim kodom predstavlja kao jedan dugi signal nakon kojeg dolaze dva kratka signala. Slika 1: prikazi mogućih slova u tajnome kodu U tajnom kodu, signali su odvojeni nizovima nula ('0'). Postoje dvije vrste nizova nula:

• Kraći niz nula: koristi se za odvajanje signala unutar jednog slova.

• Duži niz nula: koristi se za odvajanje signala između različitih slova.

Važno je napomenuti da su duljine kraćeg i dužeg niza nula različite. U tajnome kodu i kraći i duži signal moraju se pojaviti barem jednom. Tajni kod završava nekim signalom, nikad razmakom.

Inspektora Morsa zanima:

1. Koji je najmanji broj znakova koje treba izbrisati s kraja primljene poruke, tako da preostali dio poruke bude ispravan tajni kod (uvijek će biti moguće izbrisati neki broj slova da preostali dio poruke bude ispravan tajni kod).

2. Koje su duljine kratkog i dugog signala u tom tajnom kodu? Napiši program koji će za danu poruku ispisati tražene informacije.

ULAZNI PODACI

U prvom retku nalazi se prirodni broj N (1 ≤ N ≤ 40), koji predstavlja duljinu ulazne poruke.

U drugom retku nalazi se niz znakova '0' i '1' duljine N, koji predstavlja primljenu poruku.

IZLAZNI PODACI

Potrebno je ispisati tri retka:

• u prvi redak ispiši minimalni broj znakova koji su izbrisani s kraja ulazne poruke da bi ona postala ispravan tajni kod;

• u drugi redak ispiši duljinu kratkog signala (broj jedinica u kratkom signalu);

• u treći redak ispišite duljinu dugog signala (broj jedinica u dugom signalu).

Poruka uvijek započinje znakom 1.

Ulaz:

10
1101110011

Izlaz:

0
2
3

Ulaz:

9
100101011

Izlaz:

0
1
2

Ulaz:

16
1111001110001110

Izlaz:

1
3
4