Tehtäväsi on muodostaa merkkijono käyttäen kahta operaatiota:

• lisää merkkijonon perään mikä tahansa merkki (kustannus 1)
• lisää merkkijonon perään jokin merkkijonon osajono (kustannus 0)

Mikä on pienin mahdollinen kustannus?

Syöte

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

Tuloste

Tulosta pienin mahdollinen kustannus.

Rajat

• $1 \le n \le 10^6$

Esimerkki

Syöte:

abcdbc

Tuloste:

4

Selitys: Lisäät ensin merkit abcd yksi kerrallaan, mistä tulee kustannus 4. Tämän jälkeen lisäät osajonon bc ilman kustannusta ja merkkijono on valmis.