402346: GYM100735 A Strong parentheses sequence

A sequence is called a correct parenthesis sequence if it's the following form:

- Empty sequence is considered a correct parenthesis sequence.

- (A) is considered a correct parenthesis sequence.

- XY is considered a correct parenthesis sequence, if both X and Y are correct parenthesis sequences.

A sequence is called a strong parenthesis sequence only if it on form (A), where A is a correct parenthesis sequence.

You have to calculate a weird sum: take [i₁, j₁] and [i₂, j₂] every two subarrays of A. The subarrays must not intersect (i.e. i₁ ≤ i₂ and j₁ ≤ i₂) and must be strong parenthesis sequences. Then, we add to the sum the minimum length of a subarray, such as it is also a strong parenthesis sequence and it contains both [i₁, j₁] and [i₂, j₂] (i.e. if a subsequence of minimum length is [i₃, j₃], then [i₃, j₃] is a strong parenthesis sequence and also i₃ ≤ i₁ ≤ j₁ ≤ j₃ and i₃ ≤ i₂ ≤ j₂ ≤ j₃).

Output the calculated sum.

The input contains the sequence A – a strong parenthesis sequence. It's length is between 2 and 100000.

The output contains a single line - the sum requested by the problem.

(()())

6

(()(()))

16

In the first test case the answer is length of "([][])".

In the second test case the answer is the sum of lenghts of "([][()])" and "([]([]))".

(The strong parentheses sequences [i₁, j₁] and [i₂, j₂] emphasized by "[...]").