Bracket Sequences Concatenation Problem

괄호 문자열은 문자 "("와 ")"만 포함하는 문자열이다.

정규 괄호 문자열은 원래 문자열의 문자들 사이에 문자 "1"과 "+"를 삽입하여 올바른 산술식으로 변환할 수 있는 괄호 문자열이다. 예를 들어, 괄호 문자열 "()()", "(())"는 정규 괄호 문자열이며(결과로 얻는 식은 각각 "(1)+(1)", "((1+1)+1)"이다), ")("와 "("는 정규 괄호 문자열이 아니다.

n개의 괄호 문자열 $s_1$, $s_2$, ... , $s_n$가 주어진다. 괄호 문자열 $s_i$ + $s_j$가 정규 괄호 문자열이 되도록 하는 쌍 i, j (1 ≤ i, j ≤ n)의 개수를 계산한다. 연산 +는 이어 붙이기를 의미한다. 즉, "()(" + ")()" = "()()()"이다.

$s_i$ + $s_j$와 $s_j$ + $s_i$가 정규 괄호 문자열이고 i ≠ j라면, 두 쌍 (i, j)와 (j, i)를 모두 답에 포함해야 한다. 또한, $s_i$ + $s_i$가 정규 괄호 문자열이라면 쌍 (i, i)를 답에 포함해야 한다.

첫째 줄에 괄호 문자열의 개수를 나타내는 정수 하나 n (1 ≤ n ≤ 3 ⋅ $10^5$)가 주어진다. 이어지는 n개의 줄에는 문자 "("와 ")"로만 이루어진 비어 있지 않은 괄호 문자열이 주어진다. 모든 괄호 문자열의 길이의 합은 3 ⋅ $10^5$을 초과하지 않는다.

한 줄에 괄호 문자열 $s_i$ + $s_j$가 정규 괄호 문자열이 되도록 하는 쌍 i, j (1 ≤ i, j ≤ n)의 개수를 나타내는 정수 하나를 출력한다.

첫 번째 예제에서 조건을 만족하는 쌍은 (3, 1)과 (2, 2)이다.

두 번째 예제에서는 모든 쌍, 즉 (1, 1), (1, 2), (2, 1), (2, 2)가 조건을 만족한다.