Merkkijono on Lyndon-jono, jos se on aakkosjärjestyksessä pienempi
kuin kaikki sen aidot, epätyhjät loppuosat.

Tehtäväsi on etsiä annetun merkkijonon pisin osajono, joka on Lyndon-jono.

Syöte

Syötteen ainoalla rivillä on merkkijono, jossa on $n$ merkkiä väliltä a–z.

Tuloste

Tulosta yksi kokonaisluku: kuinka pitkä on merkkijonon pisin osajono, joka on Lyndon-jono.

Testit

• 1,2: $n = 10$
• 3,4: $n = 100$
• 5,6: $n = 1000$
• 7,8: $n = 5000$
• 9,10: $n = 10000$
• 11,12: $n = 100000$

Esimerkki

Syöte:

bbabaca

Tuloste:

4

Tässä tapauksessa pisin osajono on abac.