B1. Под-ПСП (простая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии вам нужно вычислить ответ только для всей строки $$$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$$$.

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

Гарантируется, что данная последовательность $$$s$$$ является правильной скобочной последовательностью.

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

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

Для каждого набора входных данных выведите одно целое число — максимальную возможную длину подпоследовательности $$$t$$$ из $$$s$$$, которая является правильной скобочной последовательностью и лучше, чем $$$s$$$. Если такой $$$t$$$ не существует, выведите $$$-1$$$.

Пример
Входные данные
3
2
()
8
(()(()))
6
(())()
Выходные данные
-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$$$, которая не лучше, чем $$$s$$$. Таким образом, мы выводим $$$6$$$.