codeforces#P990C. Bracket Sequences Concatenation Problem
Bracket Sequences Concatenation Problem
Description
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 bracket sequences . Calculate the number of pairs such that the bracket sequence is a regular bracket sequence. Operation means concatenation i.e. "()(" + ")()" = "()()()".
If and are regular bracket sequences and , then both pairs and must be counted in the answer. Also, if is a regular bracket sequence, the pair must be counted in the answer.
The first line contains one integer — the number of bracket sequences. The following lines contain bracket sequences — non-empty strings consisting only of characters "(" and ")". The sum of lengths of all bracket sequences does not exceed .
In the single line print a single integer — the number of pairs such that the bracket sequence is a regular bracket sequence.
Input
The first line contains one integer — the number of bracket sequences. The following lines contain bracket sequences — non-empty strings consisting only of characters "(" and ")". The sum of lengths of all bracket sequences does not exceed .
Output
In the single line print a single integer — the number of pairs such that the bracket sequence is a regular bracket sequence.
Samples
Note
In the first example, suitable pairs are and .
In the second example, any pair is suitable, namely .