Bessie próbuje wpisać zrównoważony ciąg nawiasów na nowym laptopie, ale duże kopyta czynią ją niezgrabną i popełnia błędy. Znajdź minimalną liczbę znaków do odwrócenia (otwierający na zamykający lub odwrotnie), aby ciąg był zrównoważony.

Jest kilka definicji równowagi. Najprostsza wymaga tyle samo nawiasów otwierających i zamykających łącznie, a w każdym prefiksie co najmniej tyle otwierających co zamykających. Te ciągi są zrównoważone:

()
(())
()(()())

Te nie są:

)(
())(
((())))

Wejście

• Wiersz 1: ciąg nawiasów $A$ parzystej długości, najwyżej 100,000 znaków.

Wyjście

• Wiersz 1: jedna liczba całkowita, minimalna liczba nawiasów do odwrócenia dla zrównoważonego ciągu.

Przykład

Wejście 1

())(

Wyjście 1

2

Uwagi

Trzeba odwrócić ostatni nawias i jeden z dwóch środkowych zamykających.

Autor zadania: Brian Dean, 2012