P15236 [NHSPC 2025] 括号问题

括号有许多种类，如：大括号 `{}`、中括号 `[]`、以及小括号 `()`。 在本题中，我们仅考虑小括号。括号通常成对使用，如果一个由括号组成的序列具有**嵌套结构 (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$ 代表最少需要删除的括号数量。

### 数据限制 * $1 \leq n \leq 10^5$。 * $P$ 仅包含 `(` 与 `)`。 ### 评分说明 本题共有三组子任务，条件限制如下所示： 每一组可能包含一或多笔测试资料，该组所有测试资料皆需答对才会获得该组分数。 | 子任务 | 分数 | 额外输入限制 | | :----: | :--: | ------------- | | 1 | 30 | 所有左括号的出现位置均早于所有右括号（因此左右括号不会交错出现）。 | | 2 | 30 | $ans$ 只可能会是 $0$ 或 $2$。（注：只需判断 $P$ 是否为「格式正确」。） | | 3 | 40 | 无额外限制。 |