Саша спокойной программировал, пока к нему не подошла Валентина и не попросила объяснить, зачем в коде нужны все эти круглые скобки. Он объяснил ей их назначение в общих чертах и дал задание, чтобы успеть закончить работу в срок.
В этой задаче мы будет рассматривать только строки, состоящие из открывающих и закрывающих круглых скобок, то есть символов «(» и «)».
Последовательность скобок называется правильной в следующих случаях:
Например, последовательности круглых скобок «()()» и «((()))(())» являются правильными, а «)(()», «(((((» и «())» — нет.
Саша взял листок и написал на нём некоторую строку s, состоящую только из открывающих и закрывающих круглых скобок, и попросил Валентину посчитать количество различных непустых подстрок строки s, являющихся правильными скобочными последовательностями. Другими словами, её задача состоит в том, чтобы посчитать количество непустых правильных скобочных последовательностей, встречающихся в s в качестве подстроки (не путать с подпоследовательностью).
Когда Валентина закончила выполнять задание, Саша вдруг осознал, что сам не знает ответа. Помогите ему не ударить в грязь лицом и решите задачу!
В первой строке входных данных записано целое число n (1 ≤ n ≤ 500 000) — длина строки s.
Во второй строке записана строка s длины n, состоящая только из символов «(» и «)».
Выведите количество различных непустых правильных скобочных последовательностей, встречающихся в s в качестве подстроки.
10
()()()()()
5
7
)(())()
3
В первой примере существует 5 различных подстрок, которые следует посчитать: «()», «()()», «()()()», «()()()()» и «()()()()()».
Во втором примере подходят 3 различные подстроки: «()», «(())» и «(())()».
