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

「$\mathtt{\text{))(()()}}$」

「$\mathtt{\text{)()(()()()}}$」

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

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

「$\mathtt{\text{)()))(()())))(()())))()()()))()()))()((()))()))))((())}}$」

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

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

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

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

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

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

一個長度為 $N$ 的字串有 $(\genfrac{}{}{0ex}{}{N+1}{2})$ 個子字串，對於任意 $1\le l\le r\le N$，$s_l{s}_{l+1}\dots s_r$ 皆為字串 $s$ 的子字串。