問題文

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

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

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

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

制約

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

入力

入力は以下の形式で標準入力から与えられる。

$S$

出力

条件を満たす整数 $(i,j)$ ($1 ≤ i ≤ j ≤ |S|$) の組の個数を出力せよ。

入力例 1

((())

出力例 1

2

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

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

入力例 2

(()()(())(

出力例 2

7