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, if si+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).

括号匹配问题，需要注意几个细节。

有以下几种情况是不能与其他组括号构成合法的括号：)(         )(((      )))(

已经是合法的括号组不需要与不合法的括号组匹配。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<stack>

 #include<deque>

 #include<map>

 #include<iostream>

 using namespace std;

 typedef long long  LL;

 const double pi=acos(-1.0);

 const double e=exp();

 const int N = ;

 #define lson i << 1,l,m

 #define rson i << 1 | 1,m + 1,r

 map<LL,LL> mp;

 char con[N];

 int main()

 {

     LL i,p,j,n,check;

     LL cont=,ans=,len1,len2;

     scanf("%lld",&n);

     getchar();

     for(j=;j<=n;j++)

     {

         p=check=;

         len1=len2=;

         memset(con,,sizeof());

         scanf("%s",con);

         for(i=;i<;i++)

         {

             if(con[i]==)

                 break;

             if(con[i]=='(')

             {

                 len1++;

                 p++;

             }

             else

             {

                 p--;

                 if(len1)

                     len1--;

                 else

                     len2++;

             }

         }

         if(len1==&&len2==)

             cont++;

         else

         {

             if(len1==)

                 mp[p]++;

             if(len2==)

                 mp[p]++;

         }

     }

     ans=cont*cont;

     map<LL,LL>::iterator it1;

     for(it1=mp.begin();it1!=mp.end();it1++)

     {

         if(it1->first>)

             break;

         if(mp[-(it1->first)]>)

             ans+=(it1->second)*mp[-(it1->first)];

     }

     printf("%lld\n",ans);

     return ;

 }