戴蒙·坦格利安决定不再看起来像 Metin2 角色。他把自己变成了最美丽的东西,一个括号序列。
对于括号序列,我们可以进行两种操作:
- 选择其子字符串$$$^\dagger$$$ 之一并将其循环移位到右侧。例如,循环右移后,“(())”将变为“)(()”;
- 在序列中任意位置插入任意括号,打开“(”或关闭“)”。
我们将括号序列的成本定义为使其平衡$$$^\ddagger$$$ 的此类操作的最小数量。
给定长度为 $$$n$$$ 的括号序列 $$$s$$$,求其所有 $$$\frac{n(n+1)}{2}$$$ 非空子串的成本总和。请注意,对于每个子字符串,我们独立计算成本。
$$$^\dagger$$$ 字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过删除开头的几个(可能是零个或全部)字符和结尾的几个(可能是零个或全部)字符从 $$$b$$$ 获得。
$$$^\ddagger$$$ 如果可以通过添加字符 $$$+$$$ 和 $$$1$$$ 将括号序列变成有效的数学表达式,则称该序列是平衡的。例如,序列“(())()”、“()”和“(()(()))”是平衡的,而“)(”、“(()”和“(()))(”则不是。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 括号序列的长度。
每个测试用例的第二行包含一个字符串 $$$s$$$,仅由字符“(”和“)”组成,长度为 $$$n$$$ — 括号序列。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - $$$s$$$ 的所有子字符串的成本总和。
示例
输入 #1
5 1 ) 4 )()( 3 ()) 5 ((((( 10 )(())))())
输出 #1
1 9 6 35 112
注意
在第一个测试用例中,只有一个子字符串“)”。它的成本是$$$1$$$,因为我们可以在这个子字符串的开头插入'('并得到一个字符串“()”,这是一个平衡字符串。
在第二个测试用例中,每个长度为 1 的子串的成本为 $$$1$$$。子字符串 ")(" 的成本是 $$$1$$$,因为我们可以循环右移它得到一个字符串 "()"。字符串 ")()" 和 "()(" 的成本是 $$$1$$$,因为它足以为它们每个插入一个括号。子字符串 ")()(" 的成本是 $$$1$$$ 因为我们可以循环右移它得到一个字符串 "()()"。所以有$$$4 + 2 + 2 + 1 = 9$$$ 成本 $$$1$$$ 的子串和 $$$1$$$ 成本 $$$0$$$ 的子串,因此成本之和为 $$$9$$$。
在第三个测试用例中,
- “(”,成本为$$$1$$$;
- “()”,成本为$$$0$$$;
- “())”,成本为$$$1$$$;
- “)”,成本为$$$1$$$;
- “))”,成本为$$$2$$$;
- “)”,成本为 $$$1$$$。
因此成本总和为 $$$6$$$。