Mirika 有一个长度为 � n 的括号序列 � s。 对于一个括号序列 � S，Mirika 可以执行两种操作： 变换：选择一个位置 � i 满足 1 ≤ � ≤ ∣ � ∣ 1≤i≤∣S∣，使得 � S 变为 � � � � + 1 ⋯ � ∣ � ∣ � 1 � 2 ⋯ � � − 2 � � − 1 S i ​ S i+1 ​ ⋯S ∣S∣ ​ S 1 ​ S 2 ​ ⋯S i−2 ​ S i−1 ​ 。 插入：在这个序列的 任意位置 插入一个括号（左右括号均可）。 Mirika 定义括号序列 � S 的权值 � ( � ) f(S) 为能将这个括号序列变成一个合法括号序列所需的最小操作数。 其中，合法括号序列的定义为： 空串为 合法括号序列。 若 A A 为 合法括号序列，则 (A) (A) 为 合法括号序列。 若 A , B A,B 均为 合法括号序列，则 AB AB 也为 合法括号序列。 现在 Mirika 想要求出： ∑ � = 1 � ∑ � = � � � ( � [ � , � ] ) ∑ l=1 n ​ ∑ r=l n ​ f(s[l,r]) 其中 � [ � , � ] s[l,r] 表示由 � � , � � + 1 , ⋯ , � � s l ​ ,s l+1 ​ ,⋯,s r ​ 形成的连续子序列。 但是 Mirika 太菜了不会算，于是只好求助于你。

好的，你的问题是：给定一个长度为 $n$ 的括号序列 $s$，定义权值 $f(S)$ 为能将 $S$ 变成一个合法括号序列所需的最小操作数，包括变换和插入两种操作。现在求 $\sum\limits_{l=1}^n\sum\limits_{r=l}^n f(s[l,r])$ 的值。其中 $s[l,r]$ 表示由 $s_l,s_{l+1},\cdots,s_r$ 形成的连续子序列。