8. Odrezané dážďovky

Žaba sa jedného dňa rozhodol ísť na prechádzku. Keďže predošlý deň výdatne pršalo, všade bolo množstvo dážďoviek. Po chvíli však našiel také, aké ešte nikdy v živote nevidel. Tieto dážďovky boli neskutočne dlhé, každá mala pozdĺž svojho tela napísané dlhé číslo neobsahujúce nuly a navyše všetky žiarili farbami od výmyslu sveta (brilantne modré, perlovorubínovo červené, opálovo zelené, antukovo hnedé, burgundské fialové, a tak podobne).

Žaba sa rozhodol, že takýchto čudesných dážďoviek by malo byť na svete viac a preto ich začne rozmnožovať delením na menšie¹. Zobral si ich za hrsť a hor’ sa na vec! Po chvíli ho to však prestalo baviť. Povedal si, že ďalšiu dažďovku už nenareže len tak, hala-bala.

Dážďovku bude rezať len medzi ciframi a každý kus musí obsahovať aspoň jednu cifru. Keď chúďa dážďovku doreže, na každom kuse musí byť číslo aspoň také veľké, ako na každom kuse naľavo od neho.

Napríklad dážďovku s číslom 11131719 môže narezať na kusy 11, 13, 17, 19 alebo na kusy 1, 1, 1, 31, 719, alebo ju môže nechať celú pokope, ale nemôže ju narezať na 111, 31, 719 pretože 31 je menej ako 111.

S takýmito pravidlami už bol spokojný, zábavy s tým bude dosť. Potom si ale uvedomil, že zistiť, koľko najviac kusov vie dostať, ak bude rezať najlepším možným spôsobom, je celkom ťažké. Vedeli by ste mu s tým pomôcť?

Úloha

Dostanete postupnosť cifier, ktorá neobsahuje nuly. Zistite, na koľko najviac čísel sa dá nasekať tak, aby každé číslo bolo aspoň také veľké, ako všetky naľavo od neho.

Formálnejšie povedané, pôvodnú postupnosť cifier \(s\) máte rozdeliť na podreťazce \(s_1, s_2, \dots, s_n\), tak, aby sme zreťazením týchto podreťazcov dostali pôvodnú postupnosť, t.j., \(s_1 s_2 \dots s_n = s\). Zároveň musí vždy platiť, že \(s_i \leq s_{i+1}\) (porovnávame číselnú hodnotu, čiže \(111 > 47\)). Máte zistiť, aké najväčšie môže byť číslo \(n\) – počet podreťazcov.

Veľmi dôležitou súčasťou vášho popisu je zdôvodnenie správnosti vášho algoritmu. Dajte si na ňom záležať.

Formát vstupu

Na jedinom riadku vstupu máte postupnosť cifier, ktorej dĺžka neprekročí \(1\,000\,000\).

Formát výstupu

Na jediný riadok vypíšte jedno číslo, najväčší možný počet kusov, na ktorý je možné nasekať dážďovku.

Príklad

Input:

1234

Output:

4

Každý kus dostane po jednej cifre.

Input:

4321

Output:

2

Nijako si nepomôžeme, jediná možnosť je sekať na 4 a 321.

Input:

11131719

Output:

6

Tu je najlepšie nasekať postupnosť na čísla 1, 1, 1, 3, 17, 19.