Problem B
Balanced Brackets

You are given a string which only consists of the characters “(” and “)”. Your task is to determine how many contiguous substrings are balanced. By balanced substring, we mean the series of parentheses could be a part of a valid mathematical expression. For example, the substrings “()”, “(())” and “()()” are balanced, while the substrings “(()”, “())” and “)(” are not balanced. Each bracket must have a corresponding bracket, and the opening bracket must come before the closing bracket.

Input

The input consists of two lines, first $N$, which specifies the amount of characters in the string. The second line contains the string S, which only consists of the characters “(” and “)”.

Output

Output the amount of contiguous balanced substrings in $S$.

Limits

• $1 \leq N \leq 10^6$

6
()(())

4

5
))(()

1