括号序列是仅包含字符“(”和“)”的字符串。
正则括号序列是通过在序列的原始字符之间插入字符“1”和“+”可以将括号序列转换为正确的算术表达式。例如,括号序列“()()”、“(())”是正则表达式(结果表达式为:“(1)+(1)”、“((1+1)+1)”),而“)(”和“(”则不是。
给你 $$$n$$$ 括号序列 $$$s_1, s_2, \dots , s_n$$$。计算对的数量 $$$i, j \, (1 \le i, j \le n)$$$ 使得括号序列 $$$s_i + s_j$$$ 是常规括号序列。操作 $$$+$$$ 表示串联,即“()(” + “)()” = “()()()”。
如果 $$$s_i + s_j$$$ 和 $$$s_j + s_i$$$ 是常规括号序列且 $$$i \ne j$$$,则 $$$(i, j)$$$ 和 $$$(j, i)$$$ 都必须计入答案中。另外,如果 $$$s_i + s_i$$$ 是常规括号序列,则 $$$(i, i)$$$ 对必须计入答案中。
输入
第一行包含一个整数 $$$n \, (1 \le n \le 3 \cdot 10^5)$$$ — 括号序列的数量。以下 $$$n$$$ 行包含括号序列 — 仅由字符“(”和“)”组成的非空字符串。所有括号序列的长度之和不超过$$$3 \cdot 10^5$$$。
输出
在单行中打印一个整数 - $$$i, j \, (1 \le i, j \le n)$$$ 的对数,使得括号序列 $$$s_i + s_j$$$ 是常规括号序列。
示例
输入 #1
3 ) () (
输出 #1
2
输入 #2
2 () ()
输出 #2
4
注意
在第一个示例中,合适的对是 $$$(3, 1)$$$ 和 $$$(2, 2)$$$。
在第二个示例中,任何对都是合适的,即 $$$(1, 1), (1, 2), (2, 1), (2, 2)$$$。