Задана скобочная последовательность \(s\), состоящая из \(n\) открывающих '(' и закрывающих ')' скобок.
Правильной скобочной последовательностью называется скобочная последовательность, которую можно преобразовать в корректное арифметическое выражение путем вставок между ее символами символов '1' и '+'. Например, скобочные последовательности «()()», «(())» — правильные (полученные выражения: «(1)+(1)», «((1+1)+1)»), а «)(» и «(» — нет.
Вы можете изменить тип какой-либо скобки \(s_i\). Это значит, что если \(s_i = \) ')', то вы можете заменить ее на '(' и наоборот.
Ваша задача — посчитать количество позиций \(i\) таких, что если вы измените тип \(i\)-й скобки, то получившаяся скобочная последовательность станет правильной.
Выходные данные
Выведите одно целое число — количество позиций \(i\) таких, что если вы измените тип \(i\)-й скобки, то получившаяся скобочная последовательность станет правильной.