Ghép Dãy Ngoặc

Một dãy ngoặc là một xâu chỉ gồm hai loại ký tự "(" và ")".

Một dãy ngoặc được gọi là đúng nếu có thể biến nó thành một biểu thức số học hợp lệ bằng cách chèn thêm các ký tự "1" và "+" vào giữa các ký tự của xâu. Ví dụ, các dãy "()()" và "(())" là đúng (tương ứng với "(1)+(1)" và "((1+1)+1)"), còn ")(" và "(" thì không đúng.

Cho $n$ dãy ngoặc $s_1,s_2,\dots ,s_n$. Hãy đếm số cặp chỉ số $(i,j)$ với $1\le i,j\le n$ sao cho dãy ngoặc $s_i+s_j$ (phép ghép nối hai xâu) là một dãy ngoặc đúng.

Ví dụ, "()(" + ")()" = "()()()".

Nếu cả $s_i+s_j$ và $s_j+s_i$ đều đúng và $i\ne j$ thì cả hai cặp $(i,j)$ và $(j,i)$ đều được tính. Nếu $s_i+s_i$ là dãy ngoặc đúng thì cặp $(i,i)$ cũng được tính.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$: số lượng dãy ngoặc.
• $n$ dòng tiếp theo, mỗi dòng chứa một dãy ngoặc: một xâu khác rỗng chỉ gồm các ký tự "(" và ")".

Dữ liệu ra

• In ra một số nguyên duy nhất: số cặp $(i,j)$ thỏa mãn $s_i+s_j$ là dãy ngoặc đúng.

Ràng buộc

• $1\le n\le 3·{10}^5$
• Tổng độ dài của tất cả các dãy ngoặc không vượt quá $3·{10}^5$.

Ví dụ