CF1750E.Bracket Cost

Daemon Targaryen decided to stop looking like a Metin2 character. He turned himself into the most beautiful thing, a bracket sequence.

For a bracket sequence, we can do two kind of operations:

• Select one of its substrings$^\dagger$ and cyclic shift it to the right. For example, after a cyclic shift to the right, "(())" will become ")(()";
• Insert any bracket, opening '(' or closing ')', wherever you want in the sequence.

We define the cost of a bracket sequence as the minimum number of such operations to make it balanced$^\ddagger$.

Given a bracket sequence $s$ of length $n$, find the sum of costs across all its $\frac{n(n+1)}{2}$ non-empty substrings. Note that for each substring we calculate the cost independently.

$^\dagger$ A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

$^\ddagger$ A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters $+$ and $1$. For example, sequences "(())()", "()", and "(()(()))" are balanced, while ")(", "(()", and "(()))(" are not.

戴蒙·坦格利安决定不再看起来像《冒险岛》（Metin2）中的角色。他将自己变成世间最美丽之物——一个括号序列。

对于一个括号序列，我们可以执行以下两种操作：

• 选取其任意一个子串$^\dagger$，并将其向右循环移位。例如，对 "(())" 向右循环移位后，得到 ")(()"；
• 在序列中任意位置插入任意一个括号，即左括号 '(' 或右括号 ')'。

我们定义一个括号序列的代价为：使其变为平衡序列$^\ddagger$ 所需的上述操作的最少次数。

给定一个长度为 $n$ 的括号序列 $s$，求其全部 $\frac{n(n+1)}{2}$ 个非空子串的代价之和。注意：对每个子串，我们独立地计算其代价。

$^\dagger$ 字符串 $a$ 是字符串 $b$ 的子串，当且仅当 $a$ 可通过从 $b$ 的开头删除若干（可能为零或全部）字符、并从 $b$ 的末尾删除若干（可能为零或全部）字符而得到。

$^\ddagger$ 若一个括号序列可通过添加字符 '+' 和 '1' 转化为一个合法的数学表达式，则称其为平衡序列。例如，"(())()"、"()" 和 "(()(()))" 是平衡序列，而 ")("、"(()" 和 "(()))(" 则不是。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the bracket sequence.

The second line of each test case contains a string $s$, consisting only of characters '(' and ')', of length $n$ — the bracket sequence.

It is guaranteed that sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示括号序列的长度。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，该字符串仅由字符 '(' 和 ')' 组成，即所给的括号序列。

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

For each test case, print a single integer — the sum of costs of all substrings of $s$.

对于每个测试用例，输出一个整数——字符串 $s$ 的所有子串的代价之和。

In the first test case, there is the only substring ")". Its cost is $1$ because we can insert '(' to the beginning of this substring and get a string "()", that is a balanced string.

In the second test case, the cost of each substring of length one is $1$. The cost of a substring ")(" is $1$ because we can cyclically shift it to right and get a string "()". The cost of strings ")()" and "()(" is $1$ because its enough to insert one bracket to each of them. The cost of substring ")()(" is $1$ because we can cyclically shift it to right and get a string "()()". So there are $4 + 2 + 2 + 1 = 9$ substring of cost $1$ and $1$ substring of cost $0$. So the sum of the costs is $9$.

In the third test case,

• "(", the cost is $1$;
• "()", the cost is $0$;
• "())", the cost is $1$;
• ")", the cost is $1$;
• "))", the cost is $2$;
• ")", the cost is $1$.

So the sum of the costs is $6$.

在第一个测试用例中，唯一的子串是 ")"。其代价为 $1$，因为我们可以在此子串开头插入 '('，从而得到字符串 "()"，这是一个平衡字符串。

在第二个测试用例中，每个长度为一的子串的代价均为 $1$。子串 ")(" 的代价为 $1$，因为我们可将其向右循环移位，得到字符串 "()"。子串 ")()" 和 "()(" 的代价均为 $1$，因为各自只需插入一个括号即可使其平衡。子串 ")()(" 的代价为 $1$，因为我们可将其向右循环移位，得到字符串 "()()"。因此，代价为 $1$ 的子串共有 $4 + 2 + 2 + 1 = 9$ 个，代价为 $0$ 的子串有 $1$ 个。故所有子串的代价之和为 $9$。

在第三个测试用例中，

• "(" 的代价为 $1$；
• "()" 的代价为 $0$；
• "())" 的代价为 $1$；
• ")" 的代价为 $1$；
• "))" 的代价为 $2$；
• ")" 的代价为 $1$。

因此，所有子串的代价之和为 $6$。