Bracket Expressions

Interview

Time limit1sMemory limit512 MB

Summary

The task is to count substrings of a bracket string that are correct bracket sequences.

Level: Medium6 of 10
Topics: Stack, Dynamic programming
Solved: No attempts yet

Problem

A bracket expression is a non-empty string made up only of opening brackets ( and closing brackets ). Such an expression is called valid if every opening bracket can be matched with some later closing bracket so that the brackets enclosed between each matched pair also form a valid bracket expression.

For example, (()())() is a valid bracket expression, while )( and ()( are not.

For his research, Bajtazar ran a program that printed one specific valid bracket expression $S$ that was essential to his work. Unfortunately, that string got lost among many other brackets that were accidentally printed both before and after it. Bajtazar was left with a single bracket string that contains the wanted expression $S$ as a contiguous fragment, but he no longer knows where $S$ begins or ends.

In despair, he asks you to find every possible position of a valid bracket expression inside the string he received. He hopes there are not too many of them.

Count how many contiguous fragments (substrings) of the given string are valid bracket expressions.

Input

The first line contains one integer $n$ ( $1 \le n \le 2\,000\,000$ ), the length of the string Bajtazar read. The second line contains $n$ brackets with no spaces: the bracket string itself.

Output

Print one integer: the number of contiguous fragments of the given string that are valid bracket expressions.

Examples3

Example 1
Input
```
10
)(())()(()
```
Expected output
```
5
```
Example 2
Input
```
2
()
```
Expected output
```
1
```
Example 3
Input
```
6
()()()
```
Expected output
```
6
```