CF2227B.Party Monster

Yousef has given you a sequence $s$ of length $n$ consisting only of characters '$\texttt{(}$' and '$\texttt{)}$'. You are allowed to perform the following operation at most once:

• Choose a substring$^{\text{∗}}$ of $s$ and remove it. Then, you may reinsert the removed characters back into the remaining string one by one. Each character can be placed at any arbitrary position, independently of the others.

Yousef wants you to determine whether it is possible to obtain a regular bracket sequence$^{\text{†}}$ after performing the operation at most once.

$^{\text{∗}}$A substring is a contiguous subsegment of a string. For example, "acab" is a substring of "abacaba" (it starts in position $3$ and ends in position $6$), but "aa" or "d" aren't substrings of this string. So the substring of the string $s$ from position $l$ to position $r$ is $s[l, r]= s_l s_{l+1} \dots s_r$.

$^{\text{†}}$A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting the characters $1$ and $+$ 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.

优素福给了你一个长度为 $n$ 的序列 $s$，其中仅包含字符 $\texttt{(}$ 和 $\texttt{)}$。你最多可以执行以下操作一次：

• 选择 $s$ 的一个子串$^{\text{∗}}$ 并将其移除；然后，你可以将被移除的字符逐个重新插入到剩余字符串中的任意位置。每个字符可被独立地放置在任意位置（彼此之间互不影响）。

优素福希望你判断：是否可以通过至多执行一次该操作，得到一个合法括号序列$^{\text{†}}$。

$^{\text{∗}}$ 子串是字符串的一个连续子段。例如，“acab” 是 “abacaba” 的一个子串（它起始于第 $3$ 个位置，终止于第 $6$ 个位置），但 “aa” 或 “d” 并不是该字符串的子串。因此，字符串 $s$ 中从位置 $l$ 到位置 $r$ 的子串为 $s[l, r] = s_l s_{l+1} \dots s_r$。

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

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

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — 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 sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

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

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

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

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

For each test case, output "YES" if the sequence can be made regular, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

对于每个测试用例，如果该序列可以变为正则序列，则输出 “YES”，否则输出 “NO”。

您可以以任意大小写形式输出答案（大写或小写）。例如，字符串 “yEs”、“yes”、“Yes” 和 “YES” 均会被识别为肯定回答。

In the first test case, the string $s$ is already a regular bracket sequence, therefore the answer is "YES".

In the second test case, we can remove the substring $s[2, 2] = \texttt{(}$ and reinsert it at the beginning of the string, making $s = \texttt{()}$, therefore the answer is "YES".

In the third test case, there is no way to do the operation and get a regular bracket sequence, so the answer is "NO".

In the fourth test case, we can choose the substring $s[3, 4] = \texttt{)(}$, remove it, then reinsert the characters as follows:

$$\\texttt{()}{\\color{red}{\\texttt{)(}}}\\texttt{()} \\to \\texttt{()()} \\to {\\color{green}{\\texttt{(}}}\\texttt{()()}{\\color{green}{\\texttt{)}}}$$

Therefore we have made a regular bracket sequence, and the answer is "YES".

在第一个测试用例中，字符串 $s$ 已经是一个合法括号序列，因此答案为 "YES"。

在第二个测试用例中，我们可以移除子串 $s[2, 2] = \texttt{(}$，并将其重新插入到字符串开头，使 $s = \texttt{()}$，因此答案为 "YES"。

在第三个测试用例中，不存在任何方式通过该操作得到合法括号序列，因此答案为 "NO"。

在第四个测试用例中，我们可以选择子串 $s[3, 4] = \texttt{)(}$，将其移除，然后按如下方式重新插入字符：

$$\texttt{()}{\color{red}{\texttt{)(}}}\texttt{()} \to \texttt{()()} \to {\color{green}{\texttt{(}}}\texttt{()()}{\color{green}{\texttt{)}}}$$

因此我们得到了一个合法括号序列，答案为 "YES"。