题目描述

括号有许多种类，如：大括号 {}、中括号 []、以及小括号()

在本题中，我们仅考虑小括号。括号通常成对使用，如果一个由括号组成的序列具有嵌套结构 (nested structure)，我们称此序列为「格式正确」。

例如：

• 序列 $A=a_1a_2\cdots a_{6}=$()(()) 是格式正确的；
• 序列 $B=b_1b_2\cdots b_{5}=$(()() 则不是格式正确的，因为没办法在满足每个右括号只能被配对一次的条件下，让每个左括号都能配对到它后面的其中一个右括号。

更正式的来说，「格式正确」可以定义如下：

一个由括号构成的序列$P=p_1p_2p_3\cdots p_n$ 为格式正确，若同时满足以下两个条件：

1. 由左到右扫描 $p_1$ 到 $p_n$，在过程中任一位置的右括号 ) 的数量都不超过左括号 ( 的数量。
2. 序列中左括号的总数等于右括号的总数。

刘老师想要让你帮助他们：计算最少需要删除多少个括号，才能让 P转换成为一个「格式正确」的序列。

输入格式

$$\begin{aligned} & n \\ & P_1P_2\cdots P_n \\ \end{aligned} $$

• $n$ 代表括号序列的长度。
• $P$ 是由 ( 和 ) 组成的括号序列。

输出格式

$$ans$$

• $ans$ 代表最少需要删除的括号数量。

6
()(())

0

5
(()()

1

3
)((

3

提示

测试数据限制

• $1 \leq n \leq 10^5$。
• $P$ 仅包含 (与 )。

评分说明

本题共有三组子任务，条件限制如下所示：每一组可能包含一或多笔测试资料，该组所有测试资料皆需答对才会获得该组分数。

子任务	分数	额外输入限制
1	30	所有左括号的出现位置均早于所有右括号（因此左右括号不会交错出现）。
2		$ans$ 只可能会是 $0$ 或 $2$。（注：只需判断 $P$ 是否为「格式正确」。）
3	40	无额外限制。