Bracket Substrings

A bracket string is defined as follows.

1. The empty string is a bracket string.
2. If $S$ is a bracket string, then $(S)$ is a bracket string.
3. If $S$ and $T$ are bracket strings, then $ST$ is a bracket string.
4. Every bracket string is built by these three rules alone.

For example, ()() and ((()))(()) are bracket strings, while )((), (((((, and ()) are not.

Given a string $S$, write a program that counts how many different bracket strings appear among the substrings of $S$. A substring is a contiguous block cut out of $S$, the empty string is not counted, and a string that occurs at several positions is counted once.

The first line contains the length of the string, $N$ ($1 \le N \le 500{,}000$).

The second line contains the string $S$. Its length is $N$ and it consists only of the opening bracket ( and the closing bracket ).

Print the number of different bracket strings among the substrings of $S$.