Nyaklánc

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