[Solution] Bracket Cost Codeforces Solution

E. Bracket Cost

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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†${}^{†}$ 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‡${}^{‡}$.

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

†${}^{†}$ 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.

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

Input

Each test consists of multiple test cases. The first line contains a single integer 𝑡$t$ (1≤𝑡≤105$1\le t\le {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≤𝑛≤2⋅105$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⋅105$2\cdot {10}^5$.

Output

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

Note

In the first test case, there is the only substring ")". Its cost is 1$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$1$. The cost of a substring ")(" is 1$1$ because we can cyclically shift it to right and get a string "()". The cost of strings ")()" and "()(" is 1$1$ because its enough to insert one bracket to each of them. The cost of substring ")()(" is 1$1$ because we can cyclically shift it to right and get a string "()()". So there are 4+2+2+1=9$4+2+2+1=9$ substring of cost 1$1$ and 1$1$ substring of cost 0$0$. So the sum of the costs is 9$9$.

In the third test case,

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

So the sum of the costs is 6