Zakręty [A]

Limit pamięci: 128 MB

Bajtazar wybrał się na wycieczkę samochodową po krętej, górskiej drodze. Roztropnie wziął ze sobą mapę, jednakże zupełnie nie jest w stanie określić, w którym miejscu mapy się aktualnie znajduje.

Ilustracja drogi na mapie zawiera zakrętów, z których każdy jest o w lewo lub w prawo. Dla uproszczenia możemy reprezentować całą mapę przez -literowy napis złożony z liter L i/lub P.

Zakładając, że Bajtazar ma właśnie przed sobą -ty zakręt na drodze (choć może tego nie wiedzieć), przez oznaczamy liczbę zakrętów, które Bajtazar musi pokonać, żeby być pewnym, w którym miejscu mapy się znajduje. Znaczenie wartości najlepiej jest rozważyć na przykładzie. Załóżmy, że droga jest reprezentowana przez napis LLPPLPL. Jeśli Bajtazar ma przed sobą aktualnie drugi zakręt, to przed przejechaniem tego zakrętu wie, że znajduje się przed jednym z zakrętów: , , albo (gdyż widzi przed sobą zakręt w lewo). Po pokonaniu jednego zakrętu (L) Bajtazar widzi przed sobą trzeci zakręt drogi - P, co oznacza, że początkowo nie mógł się on znajdować przed pierwszym zakrętem (gdyż następny byłby w lewo) ani przed ostatnim zakrętem (gdyż po jego pokonaniu zobaczyłby koniec drogi). Wie on zatem, że aktualnie znajduje się przed trzecim lub szóstym zakrętem na mapie. Pokonanie kolejnego zakrętu spowoduje, że Bajtazar zobaczy przed sobą zakręt P, co oznacza, że w chwili początkowej nie mógł się on znajdować tuż przed piątym zakrętem, gdyż w takim wypadku zobaczyłby w tym momencie zakręt w lewo. Ostatecznie pokonanie dwóch zakrętów upewnia Bajtazara, że znajduje się on przed czwartym zakrętem na drodze, a zatem .

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis drogi,
• wyznaczy wartości dla ,
• wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (). Drugi wiersz zawiera opis drogi w postaci ciągu liter L i/lub P, bez jakichkolwiek odstępów.

Wyjście

Wyjście powinno zawierać dokładnie wierszy. W -tym z nich powinna znajdować się liczba .

Przykład

Dla danych wejściowych:

7
LLPPLPL

poprawną odpowiedzią jest:

1
2
1
2
2
2
1

Autor zadania: Marek Cygan.