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 nn bracket sequences s1,s2,…,sns1,s2,…,sn. Calculate the number of pairs i,j(1≤i,j≤n)i,j(1≤i,j≤n) such that the bracket sequence si+sjsi+sj is a regular bracket sequence. Operation ++ means concatenation i.e. "()(" + ")()" = "()()()".

If si+sjsi+sj and sj+sisj+si are regular bracket sequences and i≠ji≠j, then both pairs (i,j)(i,j) and (j,i)(j,i) must be counted in the answer. Also, ifsi+sisi+si is a regular bracket sequence, the pair (i,i)(i,i) must be counted in the answer.

The first line contains one integer n(1≤n≤3⋅105)n(1≤n≤3⋅105) — the number of bracket sequences. The following nn lines contain bracket sequences — non-empty strings consisting only of characters "(" and ")". The sum of lengths of all bracket sequences does not exceed 3⋅1053⋅105.

In the single line print a single integer — the number of pairs i,j(1≤i,j≤n)i,j(1≤i,j≤n) such that the bracket sequence si+sjsi+sj is a regular bracket sequence.

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

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

题意： 给你n个只包含'('和')'的字符串，问每两个字符串相互组合后形成的完整括号（由左到右都可以匹配）的种数

首先消除每个字符串内的已匹配的括号，如果剩余的字符串还同时含有左括号和右括号，那么这种字符串是不可以和其他字符串匹配成功的，直接剔除。

最后枚举只剩余左括号的，看有多少右括号与之对应，这样避免了重复计数。

#include <map>

#include <set>

#include <cmath>

#include <queue>

#include <cstdio>

#include <vector>

#include <string>

#include <cstring>

#include <iostream>

#include <algorithm>

#define debug(a) cout << #a << " " << a << endl

using namespace std;

const int maxn = 1e6 + ;

const int mod = 1e9 + ;

typedef long long ll;

string s[maxn];

map< pair< ll, ll >, ll > mm;

ll le[maxn], ri[maxn], vis[maxn];

int main(){

    std::ios::sync_with_stdio(false);

    ll n;

    while( cin >> n ) {

        mm.clear();

        memset( le, , sizeof(le) );

        memset( ri, , sizeof(ri) );

        memset( vis, , sizeof(vis) );

        for( ll i = ; i < n; i ++ ) {

            cin >> s[i];

            ll l = , r = ;

            for( ll j = ; j < s[i].length(); j ++ ) {

                if( s[i][j] == '(' ) {

                    l ++;

                } else if( s[i][j] == ')' && l >  ) {

                    l --;

                } else if( s[i][j] == ')' && l ==  ) {

                    r ++;

                }

            }

            le[i] = l, ri[i] = r;

        }

        for( ll i = ; i < n; i ++ ) {

            if( le[i] && ri[i] ) {

                vis[i] = ;

            }

        }

        for( ll i = ; i < n; i ++ ) {

            if( !vis[i] ) {

                mm[make_pair(le[i],ri[i])] ++;

            }

        }

        ll ans = ;

        for( ll i = ; i < n; i ++ ) {

            if( !vis[i] && !ri[i] ) {

                ans += mm[make_pair(,le[i])];

            }

        }

        cout << ans << endl;

    }

    return ;

}