Nawiasy
Limit pamięci: 32 MB
Wyrażeniem nawiasowym nazwiemy niepusty ciąg składający się z nawiasów otwierających i zamykających.
Powiemy, że wyrażenie nawiasowe jest poprawne, jeżeli
każdy nawias otwierający można sparować z nawiasem zamykającym,
występującym po nim, tak aby ciąg nawiasów znajdujących się
pomiędzy nimi również był poprawnym ciągiem nawiasowym.
Na przykład (()())() jest poprawnym wyrażeniem nawiasowym,
ale )( i ()( już poprawne nie są.
Bajtazar w swojej pracy naukowej skorzystał z programu wypisującego
pewne poprawne wyrażenie nawiasowe , mające kluczowe znaczenie
dla jego badań.
Niestety, słowo to zaginęło w gąszczu innych nawiasów, które przez
przypadek mogły być wypisane zarówno przed nim, jak i po nim.
Bajtazar otrzymał więc słowo nawiasowe, które zawiera w sobie jako
spójny fragment szukane słowo , jednak nie wie, gdzie się ono zaczyna
i gdzie kończy.
Zrozpaczony, poprosił Ciebie o pomoc w wyznaczeniu wszystkich możliwych
położeń poprawnych słów nawiasowych w otrzymanym słowie.
Ma bowiem nadzieję, że jest ich niewiele ...
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą
(), oznaczającą
długość słowa, które odczytał Bajtazar.
W drugim wierszu znajduje się nawiasów (bez odstępów) - jest to
odczytane słowo nawiasowe.
Możesz założyć, że w testach wartych przynajmniej punktów zachodzi dodatkowy warunek .
Wyjście
Twój program powinien wypisać na standardowe wyjście jedną liczbę
całkowitą oznaczającą liczbę fragmentów odczytanego słowa, które są
poprawnymi słowami nawiasowymi.
Przykład
Dla danych wejściowych:
10
)(())()(()
poprawną odpowiedzią jest:
5
Autor zadania: Michał Włodarczyk.