Problem description
Dzieci grają w klasy. Gra toczy się na chodniku o wymiarach 1 × N kostek. W przeciwieństwie do standardowej gry w klasy, jedynym celem w grze jest przeskoczenie z pierwszego pola na ostatnie – nie rzuca się żadnymi kamieniami i nie trzeba skakać co jedno pole. Dla utrudnienia jednak niektóre pola są zablokowane. Wskoczenie na takie pole oznacza przegraną.
Jasio nie potrafi daleko skakać. Obawia się, że zawsze będzie przegrywał. Chciałby dowiedzieć się jaką co najmniej długość skoku musi umieć wykonać, aby móc bezpieczenie doskoczyć do mety. Pomóż mu!
Napisz program, który: wczyta opis planszy, wyznaczy minimalną długość skoku, którą trzeba móc wykonać aby przeskoczyć z pola pierwszego na ostatnie nie przeskakując ani razu przez pole zablokowane i wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N określająca długość planszy. W
drugim (i ostatnim) wierszu wejścia znajuje się ciąg długości N składający się z liter
B i W. Litera B oznacza pole
zablokowane, zaś litera W oznacza pole wolne.
Gwarantowane jest, że pierwsze oraz ostatnie pole są wolne.
Wyjście
W pierwszym (i jedynym) wierszu wyjścia powinna się znaleźć jedna liczba naturalna – minimalna długość skoku, którą Jasio musi potrafić wykonać, aby być w stanie wygrać.
Ograniczenia
1 ≤ N ≤ 1 000 000.
Przykład
| Input | Output | |
|
|