問題文

( と ) からなる文字列 S が与えられます。次の条件を満たす整数 (i,j) (1 ≤ i ≤ j ≤ |S|) の組はいくつあるでしょうか。

条件: - S の i 文字目から j 文字目まで (両端を含む) を取り出した時、その文字列は括弧の対応が取れている。

括弧の対応が取れている文字列とは、次のうちいずれかの条件を満たす文字列です。

• 空文字列
• ある括弧の対応が取れている文字列 A, B が存在し、 A, B をこの順に連結した文字列
• ある括弧の対応が取れている文字列 A が存在し、 (, A, ) をこの順に連結した文字列

制約

• 1 ≤ |S| ≤ 10^5
• S は (, ) のみからなる文字列

入力例 1

((())

出力例 1

2

• S の 2 文字目から 5 文字目までを取り出すと、 (()) です。これは括弧の対応が取れています。
• S の 3 文字目から 4 文字目までを取り出すと、 () です。これは括弧の対応が取れています。

よって、 (2, 5) および (3, 4) が条件を満たします。

入力例 2

(()()(())(

出力例 2

7