CF2190B1.Sub-RBS (Easy Version)

This is the easy version of the problem. The difference between the versions is that in this version, you only need to evaluate for whole string $s$, $s$ is regular, and the constraints on $n$ are higher.

We say that a bracket sequence $a$ is better than a bracket sequence $b$ if one of the following holds:

• $b$ is a prefix of $a$, but $a \ne b$; or
• let $i$ be the first position (if it exists) where $a_i \neq b_i$, then $\color{red}{a_i = \texttt{(}}$ and $\color{red}{b_i = \texttt{)}}$.

You are given a regular bracket sequence$^{\text{∗}}$ $s$ of even length $n$.

Among all non-empty subsequences $^{\text{†}}$ $t$ of $s$ that are regular bracket sequences, find the maximum possible length of $t$ such that $t$ is better than $s$. If no such $t$ exists, report it.

$^{\text{∗}}$A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting the characters $\texttt{1}$ and $\texttt{+}$ between the original characters of the sequence. For example:

• bracket sequences $\texttt{()()}$ and $\texttt{(())}$ are regular (the resulting expressions are $\texttt{(1)+(1)}$ and $\texttt{((1+1)+1)}$);
• bracket sequences $\texttt{)(}$, $\texttt{(}$, and $\texttt{)}$ are not.

$^{\text{†}}$A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) element from arbitrary positions.

这是该问题的简单版本。两个版本的区别在于：在本版本中，你只需对整个字符串 $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{)}}$。

给定一个长度为偶数 $n$ 的正则括号序列$^{\text{∗}}$ $s$。

在 $s$ 的所有非空子序列$^{\text{†}}$ $t$（其中 $t$ 本身也是正则括号序列）中，找出满足 $t$ 优于 $s$ 的 $t$ 的最大可能长度。若不存在这样的 $t$，请报告这一点。

$^{\text{∗}}$ 正则括号序列是指：可通过在原序列字符之间插入字符 $\texttt{1}$ 和 $\texttt{+}$，将其转化为合法算术表达式的括号序列。例如：

• 括号序列 $\texttt{()()}$ 和 $\texttt{(())}$ 是正则的（对应表达式分别为 $\texttt{(1)+(1)}$ 和 $\texttt{((1+1)+1)}$）；
• 括号序列 $\texttt{)(}$、$\texttt{(}$ 和 $\texttt{)}$ 不是正则的。

$^{\text{†}}$ 序列 $a$ 是序列 $b$ 的子序列，当且仅当 $a$ 可通过从 $b$ 中任意位置删除若干（可能为零个或全部）元素而得到。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$, $n$ is even) — the length of the string $s$.

The second line of each test case contains a sequence $s$ of length $n$ consisting only of characters $\texttt{(}$ and $\texttt{)}$.

It is guaranteed that the given sequence $s$ is a regular bracket sequence.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$，且 $n$ 为偶数）—— 字符串 $s$ 的长度。

每个测试用例的第二行包含一个长度为 $n$ 的序列 $s$，其中仅包含字符 $\texttt{(}$ 和 $\texttt{)}$。

保证给定的序列 $s$ 是一个合法括号序列（regular bracket sequence）。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, print a single integer — the maximum possible length of a non-empty subsequence $t$ of $s$ that is a regular bracket sequence and is better than $s$. If no such $t$ exists, print $-1$.

对于每个测试用例，输出一个整数——字符串 $s$ 的非空子序列 $t$ 的最大可能长度，使得 $t$ 是一个合法括号序列，且优于 $s$。若不存在这样的 $t$，则输出 $-1$。

In the first example, the only non-empty regular bracket subsequence of $s$ is $t = s = \texttt{()}$. Since $t$ is not better than $s$, we output $-1$.

In the second example, we can choose $t = \texttt{((()))}$. The first index where $t$ and $s$ differ is $i = 3$. Since $t_3 = \texttt{(}$ and $s_3 = \texttt{)}$, $t$ is better than $s$. We cannot choose a longer subsequence because the only longer regular bracket subsequence is $s$ itself, which is not better than $s$. Thus, we output $6$.

在第一个例子中，$s$ 的唯一非空正则括号子序列是 $t = s = \texttt{()}$。由于 $t$ 并不优于 $s$，我们输出 $-1$。

在第二个例子中，我们可以选择 $t = \texttt{((()))}$。$t$ 与 $s$ 首次不同的下标是 $i = 3$。由于 $t_3 = \texttt{(}$ 而 $s_3 = \texttt{)}$，因此 $t$ 优于 $s$。我们无法选择更长的子序列，因为唯一更长的正则括号子序列就是 $s$ 本身，而它并不优于 $s$。因此，我们输出 $6$。