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