E. Почти правильная скобочная последовательность
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана скобочная последовательность $$$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