Codah ClubVježbaj. Pošalji. Napreduj.
Prijavi se
Hrvatski
#000656

DNA - COCI

Biolozi su otkrili neobičnu DNA molekulu koju možemo zamisliti kao niz od N znakova od kojih je svaki A ili B. Određenim mutacijama sva su se slova ovog niza pretvorila u A. Biolozima je to bilo vrlo neobično pa su malo pomnije proučili mutacije ove molekule.


Ispostavilo se da postoje dvije vrste mutacija. Jedna vrsta mutacije promijenit će jedan element niza (dakle A → B ili B → A). Druga vrsta mutacije promijenit će neki prefiks niza, što znači da će se svako slovo od prvog do K-tog (za neki K između 1 i N, uključivo) zamijeniti sa drugim slovom (A sa B, B sa A).


Izračunajte najmanji mogući broj mutacija koji je od početnog stanja molekule mogao dovesti do konačnog stanja (u kojem su sva slova jednaka A). Mutacije se mogu događati bilo kojim redoslijedom.



InputU prvom retku ulaza nalazi se prirodan broj N (1 ≤ N ≤ 1 000 000), duljina molekule.U sljedećem retku nalazi se niz od N znakova od kojih je svaki A ili B. Taj niz predstavlja početno stanje molekule.


OutputU jedini redak izlaza ispišite traženi minimalan broj mutacija.



Input:
4
ABBA
Output:
2



Input:
5
BBABB
Output:
2



Input:
12
AAABBBAAABBB
Output:
4

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.