8575번 - Śpiew 다국어

Na lekcji śpiewu uczniowie Bajtazara siedzą w jednym, długim rzędzie. Nie wszystkie krzesła są w nim zapełnione i pomiędzy poszczególnymi uczniami mogą występować wolne miejsca.

Na lekcji uczniowie potrzebują śpiewników, ale nie każdy musi trzymać śpiewnik. Nauczyciel musi się zatroszczyć tylko o to, aby każdy uczeń bez śpiewnika siedział bezpośrednio obok ucznia ze śpiewnikiem. Ponieważ uczniowie na każdej lekcji siadają w inny sposób a śpiewników jest dosyć mało, Bajtazar poprosił Ciebie, swojego przyjaciela, o napisanie programu, który dla danego rozmieszczenia uczniów wyznaczy minimalną liczbę potrzebnych im śpiewników, aby ułatwić Bajtazarowi rozdawanie śpiewników.

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba naturalna $n$ ($1 ≤ n ≤ 1\,000\,000$) oznaczająca liczbę miejsc w rzędzie. W drugim wierszu znajduje się ciąg $n$ znaków opisujących kolejne miejsca:

• znak "W" oznacza miejsce wolne,
• znak "Z" oznacza miejsce zajęte przez ucznia.

Twój program powinien wypisać na wyjście jedną liczbę całkowitą oznaczającą minimalną liczbę śpiewników, które można rozdać uczniom tak, aby każdy miał śpiewnik lub siedział obok kogoś ze śpiewnikiem.