CF990C.Bracket Sequences Concatenation Problem

A bracket sequence is a string containing only characters "(" and ")".

A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example, bracket sequences "()()", "(())" are regular (the resulting expressions are: "(1)+(1)", "((1+1)+1)"), and ")(" and "(" are not.

You are given $n$ bracket sequences $s_1, s_2, \dots , s_n$. Calculate the number of pairs $i, j \, (1 \le i, j \le n)$ such that the bracket sequence $s_i + s_j$ is a regular bracket sequence. Operation $+$ means concatenation i.e. "()(" + ")()" = "()()()".

If $s_i + s_j$ and $s_j + s_i$ are regular bracket sequences and $i \ne j$, then both pairs $(i, j)$ and $(j, i)$ must be counted in the answer. Also, if $s_i + s_i$ is a regular bracket sequence, the pair $(i, i)$ must be counted in the answer.

括号序列是指仅由字符 ( 和 ) 组成的字符串。

正则括号序列（regular bracket sequence）是指：通过在原序列的字符之间插入字符 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)$ 也需计入答案。

The first line contains one integer $n \, (1 \le n \le 3 \cdot 10^5)$ — the number of bracket sequences. The following $n$ lines contain bracket sequences — non-empty strings consisting only of characters "(" and ")". The sum of lengths of all bracket sequences does not exceed $3 \cdot 10^5$.

第一行包含一个整数 $n \, (1 \le n \le 3 \cdot 10^5)$ —— 括号序列的数量。接下来的 $n$ 行包含括号序列 —— 仅由字符 "(" 和 ")" 组成的非空字符串。所有括号序列的长度总和不超过 $3 \cdot 10^5$。

In the single line print a single integer — the number of pairs $i, j \, (1 \le i, j \le n)$ such that the bracket sequence $s_i + s_j$ is a regular bracket sequence.

在单行中输出一个整数——满足括号序列 $s_i + s_j$ 是合法括号序列的数对 $i, j \, (1 \le i, j \le n)$ 的个数。

In the first example, suitable pairs are $(3, 1)$ and $(2, 2)$.

In the second example, any pair is suitable, namely $(1, 1), (1, 2), (2, 1), (2, 2)$.

在第一个例子中，合适的数对是 $(3, 1)$ 和 $(2, 2)$。

在第二个例子中，所有数对均合适，即 $(1, 1), (1, 2), (2, 1), (2, 2)$。