Problem Description

Given a string $ S $ consisting of ( and ), how many pairs of integers $ (i, j) $ ($1 \leq i \leq j \leq |S|$) satisfy the following condition?

Condition: - When the substring from the $ i $-th character to the $ j $-th character (inclusive) of $ S $ is extracted, the string is well-formed parentheses.

A string is well-formed parentheses if it satisfies one of the following conditions:

• It is an empty string.
• There exist well-formed parentheses strings $ A $ and $ B $, and the string is the concatenation of $ A $ and $ B $ in that order.
• There exists a well-formed parentheses string $ A $, and the string is the concatenation of (, $ A $, and ) in that order.

Input Format

The input is given from the standard input in the following format:

$ S $

Output Format

Output the number of pairs of integers $ (i, j) $ ($1 \leq i \leq j \leq |S|$) that satisfy the condition.

Sample Input and Output

Sample Input #1

((())

Sample Output #1

2

Sample Input #2

(()()(())(

Sample Output #2

7

Notes/Hints

Constraints

• $1 \leq |S| \leq 10^5$
• $ S $ is a string consisting only of ( and ).

Sample Explanation 1

• Extracting from the 2nd character to the 5th character of $ S $ gives (()), which is well-formed parentheses.
• Extracting from the 3rd character to the 4th character of $ S $ gives (), which is well-formed parentheses.

Therefore, $ (2, 5) $ and $ (3, 4) $ satisfy the condition.

见题面 Input 部分

见题面 Output 部分