Bracket Sequence Transformation Sum

Mirika has a bracket sequence s of length \(n\). She can perform the following two operations on any bracket sequence \(S\):

• Rotation: Choose an index \(i\) (\(1 \le i \le |S|\)) and transform \(S\) into
  \(S_i S_{i+1} \cdots S_{|S|} S_1 S_2 \cdots S_{i-1}\).
• Insertion: Insert a bracket (either \(\texttt{(}\) or \(\texttt{)}\)) at any position in the sequence.

A bracket sequence is valid if it is one of the following:
1. The empty string.
2. If \(A\) is valid then \( (A) \) is valid.
3. If \(A\) and \(B\) are valid then their concatenation \(AB\) is valid.

For any sequence \(S\), define its cost \(f(S)\) to be the minimum number of operations needed to transform \(S\) into a valid bracket sequence. Note that you may perform the operations in any order and at most one rotation is needed because any two rotations can be combined into one.

More precisely, if we define:

[ \begin{aligned} A &= \max(0, -\min_{\text{prefix}}(S)) \quad \text{(the number of insertions needed without rotation)},\ T &= \text{total sum of the sequence ((+1) for (\texttt{(}) and (-1) for (\texttt{)}))},\ \text{and} \quad B &= \min_{0 \leq k < |S|} \Bigl(\max(0, -\min_{j\ge0} ; P_{k}(j)\Bigr), \quad \text{where } P_{k}(j) \text{ is the prefix sum after a rotation by } k,\ \end{aligned} ]

then the cost for \(S\) is computed by taking the minimum between doing nothing and using one rotation:

[ f(S) = \max(0, T) + \min\Bigl(A,; 1 + B\Bigr). ]

Your task is to compute the sum:

[ \sum_{l=1}^{n}\sum_{r=l}^{n} f(s[l,r]), ]

where \(s[l,r]\) denotes the contiguous subsequence from \(s_l\) to \(s_r\). It is guaranteed that the length \(n\) and the subsequence sizes are small enough so that an \(O(n^3)\) solution is acceptable.

inputFormat

The first line contains a single integer \(n\) representing the length of the bracket sequence. The second line contains a string \(s\) of length \(n\) consisting of characters '\( ( \)' and '\( ) \)'.

outputFormat

Output a single integer which is the sum \(\sum_{l=1}^{n}\sum_{r=l}^{n} f(s[l,r])\).

sample

2
)(

3

</p>