P16571 [ICPC 2026 APC] Deformed Balance

题目描述

在本题中，两个字符串 $T$ 和 $U$ 的连接记为 $T+U$。

一个仅包含括号（左括号 "(" 或右括号 ")" ）的字符串是“平衡的”当且仅当它满足下列条件之一：

• 是一个空字符串。
• 是两个非空平衡字符串的连接。
• 是 $\texttt{(} + T + \texttt{)}$ 的形式，其中 $T$ 是一个平衡字符串。

例如，"()" 和 "(())()" 是平衡的，而 "()(" 和 "((()" 不是。

一个字符串是“变形的”当且仅当它满足下列条件之一：

• 是字符串 ")"。
• 是 $T+\texttt{)}+U$ 的形式，其中 $T$ 和 $U$ 都是变形的字符串。
• 是 $\texttt{(}+T+\texttt{(}$ 的形式，其中 $T$ 是变形的字符串。

例如，"()(" 和 "))()(" 是变形的，而 "()" 和 "(()" 不是。

若字符串 $T$ 是变形的，且其连接 $\displaystyle T+\texttt{)}$ 是平衡的，则称 $T$ 有“变形平衡”。例如，字符串 "()(" 具有变形平衡。

现给定一个仅由括号组成，长度为 $n$ 的字符串 $S$。在给定的数据范围下，可以证明必然存在字符串 $X$ 和 $Y$，使得 $X+S+Y$ 具有变形平衡。请你求出 $|X|+|Y|$ 的最小可能值（即 $X$ 和 $Y$ 的长度之和的最小值）。

输入格式

输入的第一行为一个整数 $t$（$1 \leq t \leq 10\,000$），表示测试用例的个数。接下来有 $t$ 组测试数据。每组测试数据包括：

第一行为一个整数 $n$（$1 \leq n \leq 10^6$）。

第二行为一个长度为 $n$，仅由 '(' 或 ')' 组成的字符串 $S$。

所有测试用例中 $n$ 的总和不超过 $10^6$。

输出格式

对于每组测试数据，输出一个整数，表示使 $X+S+Y$ 具有变形平衡的最小 $|X|+|Y|$。

输入输出样例 #1

输入 #1

3
3
()(
1
)
7
(())())

输出 #1

0
2
4

说明/提示

样例输入与输出解释 #1

对于第一个测试用例，给定的字符串已经具有变形平衡。

对于第二个测试用例，将 $X$ 和 $Y$ 都取为 "("，则连接结果为 "()("，具有变形平衡。此时 $|X|+|Y|=2$。

对于第三个测试用例，只需将 $X$ 设为 "((()"，$Y$ 为空，即可获得最小值。