括號國是一個奇怪的國家，那裡的人民非常喜歡左小括號 $\texttt{(}$ 以及右小括號 $\texttt{)}$，因此兩個括號國的人民很常使用括號語作為溝通的方式。舉例來說：

「$\texttt{))(()()}$」

「$\texttt{)()(()()()}$」

上述呈現了兩個人的對話，其中一個人在膜拜，另一個人在裝弱。

在那裡的競程選手也喜歡使用括號語來表示一道題目，像是：

「$\texttt{)()))(()())))(()())))()()()))()()))()((()))()))))((())}$」

經由翻譯後，這道題目的意思是：

「給定一個由 $\texttt{()}$ 組成的字串，請問它所有子字串的最長合法括號子序列長度總和為何？」

你不想輸給括號國的競程選手，因此請想辦法解決這個問題。

一個括號字串為合法括號若它滿足以下條件：

• 該字串的 $\texttt{(}$ 與 $\texttt{)}$ 出現次數相同
• 對於該字串的任意前綴，其 $\texttt{(}$ 的數量皆不小於 $\texttt{)}$

一個括號字串 $s_1s_2 \ldots s_N$ 的最長合法括號子序列為最長的序列 $a_1 < a_2 < \ldots < a_K$ 使 $s_{a_1}s_{a_2} \ldots s_{a_K}$ 是一個合法括號。

一個長度為 $N$ 的字串有 $\binom{N + 1}{2}$ 個子字串，對於任意 $1 \leq l \leq r \leq N$，$s_ls_{l + 1} \ldots s_r$ 皆為字串 $s$ 的子字串。