A7330 | $更优括号子序列$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一个长度为偶数的合法括号序列 $s$。 我们定义：括号序列 $a$ 比括号序列 $b$ 更优，当且仅当满足下面任一条件： - $b$ 是 $a$ 的真前缀； - 否则，设两者第一次不同的位置为 $i$，若 $a_i='('$ 且 $b_i=')'$，则认为 $a$ 更优。 现在你需要从 $s$ 中删除若干个字符（至少保留一个字符，且保留下来的相对顺序不能改变），得到一个 非空子序列 $t$。要求： - $t$ 本身也必须是合法括号序列； - $t$ 比原串 $s$ 更优。 请求出满足条件的 $t$ 的最大可能长度；若不存在这样的 $t$，输出 $-1$。

第一行一个整数 $t$，表示测试组数。 对于每组数据： - 第一行一个整数 $n$，表示串长； - 第二行一个长度为 $n$ 的括号串 $s$。 保证给定的 $s$ 一定是合法括号序列。

对每组数据输出一个整数，表示答案；若不存在则输出 $-1$。

输入 #1

3
2
()
8
(()(()))
6
(())()

输出 #1

-1
6
-1

C++ 编辑器

输入

输出