Деймон Таргариен решил перестать быть похожим на персонажа Metin2. Он превратил себя в прекраснейшую вещь — скобочную последовательность.
Для последовательности скобок мы можем выполнять два вида операций:
- Выберите одну из её подстрок\(^\dagger\) и циклически сдвиньте её вправо. Например, после циклического сдвига вправо «(())» станет «)(()»;
- Вставьте любую скобку, открывающую «(» или закрывающую «)», в любом месте последовательности.
Мы определяем стоимость скобочной последовательности как минимальное количество таких операций, чтобы сделать её правильной\(^\ddagger\).
Для заданной скобочной последовательности \(s\) длины \(n\) найдите сумму стоимостей всех \(\frac{n(n+1)}{2}\) её непустых подстрок. Обратите внимание, что для каждой подстроки мы вычисляем стоимость независимо.
\(^\dagger\) Строка \(a\) является подстрокой \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.
\(^\ddagger\) Последовательность скобок называется правильной, если её можно превратить в правильное математическое выражение, добавив символы \(+\) и \(1\). Например, последовательности «(())()», «()» и «(()(()))» правильные, в то время как «)(», «(()» и «(()))(» не являются правильными.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — сумму стоимостей всех подстрок \(s\).
Примечание
В первом наборе входных данных есть единственная подстрока «)». Её стоимость \(1\), потому что мы можем вставить «(» в начало этой подстроки и получить строку «()», то есть сбалансированную строку.
Во втором наборе входных данных стоимость каждой подстроки длины один равна \(1\). Стоимость подстроки «)(» равна \(1\), потому что мы можем циклически сдвинуть ее вправо и получить строку «()». Стоимость строк « )()» и «()(» равна \(1\), потому что достаточно вставить по одной скобке в каждую из них. Стоимость подстроки «)()(» равна \(1\), потому что мы можем циклически сдвинуть её вправо и получить строку «()()». Таким образом, есть \(4 + 2 + 2 + 1 = 9\) подстрока стоимостью \(1\) и \(1\) подстрока из стоимостью \(0\). Таким образом, сумма стоимостей равна \(9\).
В третьем наборе входных данных:
- «(», стоимость равна \(1\);
- «()», стоимость равна \(0\);
- «())», стоимость равна \(1\);
- «)», стоимость равна \(1\);
- «))», стоимость равна \(2\);
- «)», стоимость равна \(1\).
Таким образом, сумма стоимостей равна \(6\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1
)
4
)()(
3
())
5
(((((
10
)(())))())
|
1
9
6
35
112
|