Скобочной последовательностью называется строка, состоящая только из символов «(» и «)».
Правильной скобочной последовательностью называется скобочная последовательность, которую можно преобразовать в корректное арифметическое выражение путем вставок между ее символами символов «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)\) должна учитываться в ответе.
Выходные данные
В единственной строке выведите целое число — количество пар \(i, j \, (1 \le i, j \le n)\), таких, что скобочная последовательность \(s_i + s_j\) является правильной скобочной последовательностью.
Примечание
В первом тестовом примере подходящие пары \((3, 1)\) и \((2, 2)\).
Во втором тестовом примере любая пара подходит, а именно \((1, 1), (1, 2), (2, 1), (2, 2)\).