Bracket Sequence

Problem Source

Click here

Problem Description

A valid bracket sequence is defined as follows:

1. The empty sequence is a valid bracket sequence.
2. If $S$ is a valid bracket sequence, then $(S)$ is a valid bracket sequence.
3. If $A$ and $B$ are both valid bracket sequences, then $AB$ is a valid bracket sequence.

You are given a bracket sequence. Count how many of its non-empty substrings are valid bracket sequences.

Note: for convenience, five samples are provided, but they are placed in a single box.

Input Format

A string $S$.

Output Format

The number of non-empty substrings that are valid bracket sequences.

Sample Input

(
()
()()
(()
(())

Sample Output

0
1
3
1
2

Constraints

$1 \le |S| \le 10^6$