Правильная скобочная последовательность — это скобочная последовательность, которую можно превратить в корректное арифметическое выражение, вставив символы '1' и '+' между исходными символами. Например:
- скобочные последовательности «()()» и «(())» — правильные (из них можно получить выражения «(1)+(1)» и «((1+1)+1)»);
- скобочные последовательности «)(», «(» и «)» — неправильные.
Давайте определим инверсию скобочной последовательности следующим образом: заменить все скобки '(' на ')', и наоборот (все скобки ')' на '('). Например, строки «()((» и «)())» являются инверсиями друг друга.
Задана правильная скобочная последовательность \(s\). Ваша задача — посчитать количество таких пар целых чисел \((l,r)\) (\(1 \le l \le r \le |s|\)), что если заменить всю подстроку \(s\) с \(l\)-го символа по \(r\)-й символ (включительно) на ее инверсию, \(s\) все еще будет правильной скобочной последовательностью.
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество пар \((l,r)\), удовлетворяющих условию задачи.
Примечание
В первом примере есть только одна пара:
- \((2, 3)\): (()) \(\rightarrow\) ()().
Во втором примере подходящих пар нет.
В третьем примере есть три подходящих пары:
- \((2, 3)\): ()()() \(\rightarrow\) (())();
- \((4, 5)\): ()()() \(\rightarrow\) ()(());
- \((2, 5)\): ()()() \(\rightarrow\) (()());
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
(())
()
()()()
(()())(())
|
1
0
3
13
|