给定一个括号序列 $$$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$$$ 括号的类型,则生成的括号序列将变为规则的。
示例
输入 #1
6 (((())
输出 #1
3
输入 #2
6 ()()()
输出 #2
0
输入 #3
1 )
输出 #3
0
输入#4
8 )))(((((
输出#4
0