A16566. Sub-RBS (Easy Version)
编程题
普及+/提高
知识点
题目描述
本题为该问题的简单版本。不同版本间的差异在于：本版本仅需针对完整字符串 $s$ 进行求解，且保证 $s$ 是正则括号序列，同时对 $n$ 的约束条件更宽松。
我们称括号序列 $a$ 比括号序列 $b$ **更优**，当且仅当满足以下任一条件：
1. $b$ 是 $a$ 的前缀，但 $a \ne b$；
2. 设 $i$ 是 $a$ 和 $b$ 第一个出现字符不同的位置（若存在），且满足 $a_i = \texttt{(}$ 且 $b_i = \texttt{)}$。
给定一个长度为偶数 $n$ 的**正则括号序列**$^{∗}$ $s$。
在 $s$ 的所有非空子序列$^{†}$ 中，找出满足以下条件的正则括号序列 $t$：
- $t$ 是正则括号序列；
- $t$ 比 $s$ 更优。
请输出满足条件的 $t$ 的最大可能长度。若不存在这样的 $t$，请输出 $-1$。
$^{∗}$ 正则括号序列（Regular Bracket Sequence, RBS）的定义：将序列中原有字符间插入字符 $\texttt{1}$ 和 $\texttt{+}$ 后，能转化为合法算术表达式的括号序列。例如：
- 括号序列 $\texttt{()()}$ 和 $\texttt{(())}$ 是正则的（转化后的表达式分别为 $\texttt{(1)+(1)}$ 和 $\texttt{((1+1)+1)}$）；
- 括号序列 $\texttt{)(}$、$\texttt{(}$ 和 $\texttt{)}$ 不是正则的。
$^{†}$ 子序列的定义：若序列 $a$ 可通过删除序列 $b$ 中任意位置的若干个（可能为 0 个或全部）元素得到，则称 $a$ 是 $b$ 的子序列。
我们称括号序列 $a$ 比括号序列 $b$ **更优**，当且仅当满足以下任一条件：
1. $b$ 是 $a$ 的前缀，但 $a \ne b$；
2. 设 $i$ 是 $a$ 和 $b$ 第一个出现字符不同的位置（若存在），且满足 $a_i = \texttt{(}$ 且 $b_i = \texttt{)}$。
给定一个长度为偶数 $n$ 的**正则括号序列**$^{∗}$ $s$。
在 $s$ 的所有非空子序列$^{†}$ 中，找出满足以下条件的正则括号序列 $t$：
- $t$ 是正则括号序列；
- $t$ 比 $s$ 更优。
请输出满足条件的 $t$ 的最大可能长度。若不存在这样的 $t$，请输出 $-1$。
$^{∗}$ 正则括号序列（Regular Bracket Sequence, RBS）的定义：将序列中原有字符间插入字符 $\texttt{1}$ 和 $\texttt{+}$ 后，能转化为合法算术表达式的括号序列。例如：
- 括号序列 $\texttt{()()}$ 和 $\texttt{(())}$ 是正则的（转化后的表达式分别为 $\texttt{(1)+(1)}$ 和 $\texttt{((1+1)+1)}$）；
- 括号序列 $\texttt{)(}$、$\texttt{(}$ 和 $\texttt{)}$ 不是正则的。
$^{†}$ 子序列的定义：若序列 $a$ 可通过删除序列 $b$ 中任意位置的若干个（可能为 0 个或全部）元素得到，则称 $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$。
每组测试用例的第一行输入一个整数 $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$。
输入输出样例
输入 #1
3 2 () 8 (()(())) 6 (())()
输出 #1
-1 6 -1
说明/提示
第一个样例中，$s$ 唯一的非空正则括号子序列就是 $t = s = \texttt{()}$。由于 $t$ 并不比 $s$ 更优，因此输出 $-1$。
第二个样例中，可选择 $t = \texttt{((()))}$。$t$ 和 $s$ 第一个出现差异的位置是 $i=3$：$t_3 = \texttt{(}$ 而 $s_3 = \texttt{)}$，因此 $t$ 比 $s$ 更优。无法选择更长的子序列，因为唯一更长的正则括号子序列是 $s$ 本身，而它并不比自身更优。因此输出 $6$。
第二个样例中，可选择 $t = \texttt{((()))}$。$t$ 和 $s$ 第一个出现差异的位置是 $i=3$：$t_3 = \texttt{(}$ 而 $s_3 = \texttt{)}$，因此 $t$ 比 $s$ 更优。无法选择更长的子序列，因为唯一更长的正则括号子序列是 $s$ 本身，而它并不比自身更优。因此输出 $6$。