Wstęp do programowania w C++

Bajtech to bardzo zaawansowana bajtocka firma technologiczna. Ostatnio wyprodukowali nowy, rewolucyjny smartfon, który (według reklamy) każdy szanujący się człowiek musi mieć. Ludzie tłumnie przyszli kupić nowy sprzęt, więc kolejki pod salonami sprzedaży zaczęły się tworzyć na długo przed otwarciem.

Bajtek, który nie do końca dowierza reklamom, przygląda się z daleka sytuacji przy jednym z salonów sprzedaży. Zauważył, że ludzie stojący w kolejce zachowują się bardzo kulturalnie i przewidywalnie.

Do salonu prowadzi chodnik ułożony z N płytek. Na każdej płytce może stać co najwyżej jeden człowiek. Co sekundę każdy z czekających w kolejce sprawdza, czy może przesunąć się do przodu. Jeżeli płytka przed nim jest pusta, to przechodzi na nią. Jeżeli znajduje się na ostatniej płytce, to wchodzi do salonu. Natomiast, jeśli ma przed sobą zajętą płytkę, to zostaje na swoim miejscu.

Salon właśnie się otwiera. Ile czasu zajmie, aż wszyscy, którzy obecnie czekają w kolejce, wejdą do sklepu?

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N (1 ≤ N ≤ 200 000) określająca liczbę płytek przed salonem sprzedaży. W drugim wierszu wejścia znajduje się ciąg N znaków określających stan kolejnych płytek w momencie otwarcia sklepu. Pierwszy znak opisuje koniec kolejki, a ostatni — jej początek. Znak X oznacza, że na płytce znajduje się człowiek, zaś znak . (kropka) oznacza, że płytka jest pusta.

Możesz założyć, że przynajmniej jeden klient czeka w kolejce, a więc na wejściu znajduje się co najmniej jeden znak X.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba naturalna — czas w sekundach, po którym wszyscy klienci wejdą do sklepu.

Ocenianie Możesz rozwiązać zadanie w kilku prostszych wariantach — niektóre grupy testów spełniają pewne dodatkowe ograniczenia. Poniższa tabela pokazuje, ile punktów otrzyma Twój program, jeśli przejdzie testy z takim ograniczeniem.

Example

Input:
5
X.XX.

Output:
6

Wyjaśnienie do przykładu: Sytuacją początkową oraz w kolejnych sekundach przedstawia poniższy rysunek:

Input:
6
..X...

Output:
4

Input:
13
X.XX.XXX.XXXX

Output:
19

Pozostałe testy przykładowe:

• N = 1 000, ludzie stoją na co drugiej płytce, pierwszy człowiek stoi na początku kolejki;
• N = 200 000, na każdej płytce stoi człowiek.