Беси только что купила новый лэптоп. Однако ей неудобно работать с клавиатурой, поэтому она набирает строки из круглых скобок. Она может ошибиться и набрать ( вместо ) и наоборот.
Посчитайте количество мест в строке таких, что замена одной скобки на противоположную в этом месте сделает строку сбалансированной.
Есть несколько способов определить, что такое "сбалансированная" строка скобок. Например, так: 1) Всего должно быть одинаковое количество левых ( и правых ) скобок и для любого префикса этой строки, левых скобок должно быть не меньше чем правых.
Следующие строки сбалансированы () (()) ()(()())
А эти - нет:
)( ())( ((())))
PROBLEM NAME: typo
Формат входных данных
* Строка 1: строка из скобок с длиной N (1 <= N <= 100,000).
Формат выходных данных
* Line 1: количество позиций в этой строке, (если они вообще есть), таких, что замена одной скобки на противоположную в этой позиции приведет к тому, что строка станет сбалансированной.
Примечание
Для исходной строки:
12345678 ()(())))
Замена скобки в позиции 2 приводит к такой сбалансированной строке
12345678 (((())))
Аналогично сбалансированные строки получается при замене скобок в позициях 5, 6, и 7.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
()(())))
|
4
|