Определите минимальное количество символов в строке из круглых скобок, которые нужно заменить на противоположный ( левую скобку на правую, или наоборот) , чтобы получить сбалансированную строку.
Существует несколько способов определить сбалансированную строку скобок. Например, такой: В строке должно быть одинаковое количество левых и правых скобок, и для любого ее префикса количество левых скобок должно быть не меньше, чем количество правых скобок.
Например, эти строки - сбалансированные () (()) ()(()())
А эти - нет: )( ())( ((())))
PROBLEM NAME: clumsy
Формат входных данных
* Строка 1: строка из скобок длиной не более 100,000 символов.
Формат выходных данных
* Строка 1: Одно целое число - минимальное количество скобок, которые нужно "переключить" , чтобы конвертировать заданную строку в сбалансированную.
Примечание
Последняя скобка должна быть переключена и одна из двух средних.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
())(
|
2
|