C. Конкатенация скобочных последовательностей
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Скобочной последовательностью называется строка, состоящая только из символов «(» и «)».

Правильной скобочной последовательностью называется скобочная последовательность, которую можно преобразовать в корректное арифметическое выражение путем вставок между ее символами символов «1» и «+». Например, скобочные последовательности «()()», «(())» — правильные (полученные выражения: «(1)+(1)», «((1+1)+1)»), а «)(» и «(» — нет.

Вам задано $$$n$$$ скобочных последовательностей $$$s_1, s_2, \dots , s_n$$$. Найдите количество пар $$$i, j \, (1 \le i, j \le n)$$$, таких что скобочная последовательность $$$s_i + s_j$$$ является правильной скобочной последовательностью. Операция $$$+$$$ означает конкатенацию, т. е. "()(" + ")()" = "()()()".

Если $$$s_i + s_j$$$ и $$$s_j + s_i$$$ являются правильными скобочными последовательностями и $$$i \ne j$$$, в ответе должны учитываться обе пары $$$(i, j)$$$ и $$$(j, i)$$$. Также если строка $$$s_i + s_i$$$ является правильной скобочной последовательностью, пара $$$(i, i)$$$ должна учитываться в ответе.

Входные данные

В первой строке задано число $$$n \, (1 \le n \le 3 \cdot 10^5)$$$ — количество скобочных последовательностей. В следующих $$$n$$$ строках содержатся скобочные последовательности — непустые строки, состоящие только из символов «(» и «)». Сумма длин всех скобочных последовательностей не превосходит $$$3 \cdot 10^5$$$.

Выходные данные

В единственной строке выведите целое число — количество пар $$$i, j \, (1 \le i, j \le n)$$$, таких, что скобочная последовательность $$$s_i + s_j$$$ является правильной скобочной последовательностью.

Примеры
Входные данные
3
)
()
(
Выходные данные
2
Входные данные
2
()
()
Выходные данные
4
Примечание

В первом тестовом примере подходящие пары $$$(3, 1)$$$ и $$$(2, 2)$$$.

Во втором тестовом примере любая пара подходит, а именно $$$(1, 1), (1, 2), (2, 1), (2, 2)$$$.