这是问题的简单版本。版本之间的区别在于,在这个版本中,您只需要计算整个字符串 $$$s$$$,$$$s$$$ 是 常规,并且对 $$$n$$$ 的约束更高.
我们说括号序列 $$$a$$$ 是 更好 比括号序列 $$$b$$$ 如果满足以下条件之一:
- $$$b$$$ 是 $$$a$$$ 的前缀,但 $$$a \ne b$$$;或
- 设 $$$i$$$ 为 $$$a_i \neq b_i$$$ 的第一个位置(如果存在),然后是 $$$\color{red}{a_i = \texttt{(}}$$$ 和 $$$\color{red}{b_i = \texttt{)}}$$$。
您将获得 常规括号序列$$$^{\text{*}}$$$ $$$s$$$ 偶数长度 $$$n$$$。
其中非空 子序列 $$$^{\text{†}}$$$ $$$t$$$ 的 $$$s$$$ 是 常规括号序列,找到 $$$t$$$ 的最大可能长度,使得 $$$t$$$ 为 更好 比 $$$s$$$。如果不存在这样的$$$t$$$,则报告它。
$$$^{\text{*}}$$$常规括号序列是通过在序列的原始字符之间插入字符 $$$\texttt{1}$$$ 和 $$$\texttt{+}$$$ 可以将其转换为正确的算术表达式的括号序列。例如:
- 括号序列 $$$\texttt{()()}$$$ 和 $$$\texttt{(())}$$$ 是正则表达式(结果表达式为 $$$\texttt{(1)+(1)}$$$ 和 $$$\texttt{((1+1)+1)}$$$);
- 括号序列 $$$\texttt{)(}$$$、$$$\texttt{(}$$$ 和 $$$\texttt{)}$$$ 不是。
$$$^{\text{†}}$$$ 序列 $$$a$$$ 是序列 $$$b$$$ 的子序列,如果 $$$a$$$ 可以通过从任意位置删除几个(可能是零个或全部)元素从 $$$b$$$ 获得。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$n$$$ 是偶数) — 字符串 $$$s$$$ 的长度。
每个测试用例的第二行包含一个长度为 $$$n$$$ 的序列 $$$s$$$,仅由字符 $$$\texttt{(}$$$ 和 $$$\texttt{)}$$$ 组成。
保证给定的序列 $$$s$$$ 是一个 常规括号序列.
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - $$$s$$$ 的非空子序列 $$$t$$$ 的最大可能长度,即 常规括号序列 并且是 更好 比 $$$s$$$。如果不存在这样的$$$t$$$,则打印$$$-1$$$。
示例
输入复制
32()8(()(()))6(())()
输出复制
-16-1
注意
在第一个示例中,$$$s$$$ 的唯一非空正则括号子序列是 $$$t = s = \texttt{()}$$$。由于 $$$t$$$ 并不比 $$$s$$$ 更好,因此我们输出 $$$-1$$$。
在第二个例子中,我们可以选择 $$$t = \texttt{((()))}$$$。 $$$t$$$ 和 $$$s$$$ 不同的第一个索引是 $$$i = 3$$$。由于 $$$t_3 = \texttt{(}$$$ 和 $$$s_3 = \texttt{)}$$$,$$$t$$$ 比 $$$s$$$ 更好。我们不能选择更长的子序列,因为唯一更长的正则括号子序列是 $$$s$$$ 本身,它并不比 $$$s$$$ 更好。因此,我们输出$$$6$$$。