Bracket Cost
Contest: CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 2400
Tags: binary search, data structures, divide and conquer, dp, greedy, strings

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.

Input format:
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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
5
1
)
4
)()(
3
())
5
(((((
10
)(())))())

Example output:
1
9
6
35
112

Editorial:
Let $$$a_i=1$$$ if $$$s_i=($$$, $$$a_i=-1$$$ if $$$s_i=)$$$ and $$$b_i$$$ be the prefix sum of $$$a_i$$$. Theorem: the cost of $$$s[l+1,r]$$$ is $$$max(b_l,b_r)-min(b_l,b_{l+1},...,b_r)$$$ Necessity: after one operation, $$$max(b_l,b_r)-min(b_l,b_{l+1},...,b_r)$$$ decrease at most one. Sufficiency: If $$$b_l<b_r$$$, we can do operation 2, add a right bracket at the end of string. If $$$b_l>b_r$$$, we can do operation 2, add a left bracket at the beginning of string. If $$$b_l=b_r$$$, assume x be the largest x that $$$b_x=min(b_l,b_{l+1},...,b_r)$$$, then $$$s_x=($$$, so we can do operation 1, cyclic shift $$$s[l,x]$$$ to right. Under any condition, $$$max(b_l,b_r)-min(b_l,b_{l+1},...,b_r)$$$ decrease one after one operation. We can use binary index tree to calculate $$$max(b_l,b_r)$$$ and $$$min(b_l,b_{l+1},...,b_r)$$$.