← 返回题目列表

Codeforces · 1095/E

E. 几乎规则的括号序列

中文机器翻译题面 查看原题

给定一个括号序列 $$$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