说明

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

在本题中，我们仅考虑小括号。括号通常成对使用，如果一个由括号组成的序列具有嵌套结构 (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. 序列中左括号的总数等于右括号的总数。

PorgramText 是一家软件公司，正在为程序员开发一款全新的文本编辑器。这款编辑器将提供许多强大的功能，其中之一是自动修正输入错误。

在观察使用者的输入行为后，PorgramText 发现许多程序员因打字速度太快，常常不小心多输入左括号或右括号。为了解决这个问题，编辑器将提供一项功能：将一个可能「格式不正确」的括号序列 $P$ 自动转换为「格式正确」的序列 $P^\prime$。在转换过程中，唯一允许的操作是删除左括号或右括号。

PorgramText 想要让你帮助他们：计算最少需要删除多少个括号，才能让 $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	无额外限制。