← 返回题目列表

Codeforces · 990/C

C. 括号序列串联问题

中文机器翻译题面 查看原题

括号序列是仅包含字符“(”和“)”的字符串。

正则括号序列是通过在序列的原始字符之间插入字符“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)$$$。