CF2206M 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 对于第一个测试用例，给定的字符串已经具有变形平衡。 对于第二个测试用例，将 $X$ 和 $Y$ 都取为 "("，则连接结果为 "()("，具有变形平衡。此时 $|X|+|Y|=2$。 对于第三个测试用例，只需将 $X$ 设为 "((()"，$Y$ 为空，即可获得最小值。 由 ChatGPT 5 翻译