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