B. Party Monster
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Юсеф дал вам последовательность $$$s$$$ длины $$$n$$$, состоящую только из символов '$$$\texttt{(}$$$' и '$$$\texttt{)}$$$'. Вам разрешается выполнить следующую операцию не более одного раза:

  • Выберите подстроку$$$^{\text{∗}}$$$ строки $$$s$$$ и удалите её. Затем вы можете вставить удалённые символы обратно в оставшуюся строку по одному. Каждый символ можно вставить в любое произвольное место, независимо от остальных.

Юсеф хочет, чтобы вы определили, можно ли получить правильную скобочную последовательность$$$^{\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{)}$$$ — не являются.
Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длину строки $$$s$$$.

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$, состоящую только из символов '$$$\texttt{(}$$$' и '$$$\texttt{)}$$$'.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите «YES», если последовательность можно сделать правильной, и «NO» в противном случае.

Ответ можно выводить в любом регистре (верхнем или нижнем). Например, строки «yEs», «yes», «Yes», и «YES» будут распознаны как положительные ответы.

Пример
Входные данные
6
2
()
2
)(
3
(((
6
())(()
4
(()(
5
)()()
Выходные данные
YES
YES
NO
YES
NO
NO
Примечание

В первом наборе входных данных строка $$$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».