Mint ismert, Jancsika tavaly elveszített egy fogadást Juliskával szemben, ezért most készítenie kell neki egy nyakláncot színes gyöngyökből. El is készült az N gyöngyszemből álló nyaklánc, ekkor azonban Jancsinak eszébe jutott, hogy Juliskának elég érdekes az ízlése a nyakláncok terén. Tudniillik Juliska csak olyan nyakláncokat hajlandó hordani, ami entrópiailag korrekt, vagyis az azonos színű gyöngyök egymás mellett helyezkednek el.
Jancsika nem esett kétségbe, tudta mit kell tennie: össze kell rendezni a gyöngyöket a nyakláncon a színük szerint. Tudta, hogy bármely gyöngyöt le tudja szedni és bárhova vissza is tudja rakni, de egyszerre csak kettőt tud leszedni, mert különben szétgurulhatnak, így Jancsika egy lépésben fel tud cserélni két gyöngyöt.
Segítsetek Jancsikának: írjatok programot, ami kiszámolja, hogy legkevesebb hány gyöngycsere szükséges ahhoz, hogy az azonos színű gyöngyök egymás mellett helyezkedjenek el.
Feladat
Adott egy nyaklánc, ami topológiailag egy kör, tehát nincs kitüntetett pontja. Ezen a nyakláncon szorosan fel van fűzve N db gyöngy. Minden gyöngy színe arany, vagy bugyikék lehet. Egy nyakláncot entrópiailag korrektnek nevezünk, ha az azonos színű gyöngyök mind egymás mellett vannak, egy folytonos szakaszt alkotva. Egy lépésben felcserélhetjük bármely két gyöngyöt. Kérdés: mi az a minimális lépészám, ami alatt a nyaklánc entrópiailag korrektté tehető.
Bemenet
A bemenet egyetlen string-et tartalmaz (hossza N). Minden karakter 'a', vagy 'b' lehet. Az i. karakter az i. gyöngy szinét jelenti (tetszőleges kezdőpozícióval és körüljárással, mert ugye a nyakláncnak nincs eleje vagy vége).
Kimenet
Egyetlen számot várunk a kimenetre: azt a minimális csereszámot, amivel a nyaklánc entrópiailag korrektté tehető.
Pontozás
Minden egyes teszteset helyes megoldása 1 pontot ér. összesen 100 teszteset van, így maximálisan 100 pont kapható a feladatra.
Limitek
1 <= N <= 1000000
Azon belül 10 teszteset van, ahol N <= 10
További 20 teszteset, ahol N <= 1000
Időkorlát: 2 másodperc
Memória korlát: 256MB
Példa
Bemenet
aabababaa
Kimenet
1
Magyarázat
aaBabAbaa
Elég a két nagybetűvel jelölt gyöngyöt felcserélni egymással, amivel a következő eredményt kapjuk:
aaaabbbaa
Bemenet
aaabbbaa
Kimenet
0