题目描述

给定一个由 $n$ 个左括号 '(' 和右括号 ')' 组成的括号序列 $s$。

一个“正规括号序列”是指可以通过在原序列的字符之间插入字符 '1' 和 '+'，将其转化为一个正确的算术表达式。例如，括号序列 "()()"、"(())" 是正规括号序列（对应的表达式为 "(1)+(1)"、"((1+1)+1)"），而 ")(" 和 "(" 则不是。

你可以将某些括号 $s_i$ 的类型进行更改。也就是说，如果 $s_i =$ ')'，你可以将其改为 '('，反之亦然。

你的任务是计算有多少个位置 $i$，使得如果你将第 $i$ 个括号的类型更改后，得到的括号序列会变成一个正规括号序列。

输入格式

输入的第一行包含一个整数 $n$（$1 \le n \le 10^6$），表示括号序列的长度。

第二行包含一个由 $n$ 个左括号 '(' 和右括号 ')' 组成的字符串 $s$。

输出格式

输出一个整数，表示有多少个位置 $i$ 满足：如果你将第 $i$ 个括号的类型更改后，得到的括号序列会变成一个正规括号序列。

说明/提示

由 ChatGPT 4.1 翻译

样例

6
(((())

3

6
()()()

0

1
)

0

8
)))(((((

0