У Монокарпа была правильная скобочная последовательность \(s\) длины \(n\) (\(n\) — четное). Он даже придумал свой способ вычисления её стоимости.
Он знает, что в правильной скобочной последовательности (ПСП) каждой открывающей скобке соответствует парная ей закрывающая скобка. Поэтому он решил вычислить стоимость ПСП как сумму расстояний между парами соответствующих скобок.
Например, рассмотрим ПСП (())(). Она состоит из трех пар скобок:
- (__)__: расстояние между скобками на позициях \(1\) и \(4\) равно \(4 - 1 = 3\);
- _()___: расстояние равно \(3 - 2 = 1\);
- ____(): расстояние равно \(6 - 5 = 1\).
Таким образом, стоимость
(())() равна
\(3 + 1 + 1 = 5\).
К сожалению, из-за повреждения данных Монокарп потерял все символы на нечетных позициях \(s_1, s_3, \dots, s_{n-1}\). Остались только символы на четных позициях (\(s_2, s_4, \dots, s_{n}\)). Например, (())() превратилась в _(_)_).
Монокарп хочет восстановить свою ПСП, разместив скобки на нечетных позициях. Но поскольку восстановленная ПСП может быть не уникальной, он хочет выбрать ПСП с минимальной стоимостью. Эта задача слишком сложна для Монокарпа, поэтому можете ли вы помочь ему?
Напоминание: Правильная скобочная последовательность — это строка, состоящая только из скобок, такая что эта строка, когда в неё вставляются 1-ы и +-ы, дает корректное математическое выражение. Например, (), (()) или (()())() являются ПСП, в то время как ), ()( или ())(() — не являются.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальную стоимость правильной скобочной последовательности, которую можно получить из \(s\), заменив '_' на скобки.
Примечание
В первом наборе оптимально сделать \(s\) равной (())(). Стоимость \(s\) будет равна \(3 + 1 + 1 = 5\).
Во втором наборе единственный вариант — сделать \(s\) равной () со стоимостью \(1\).
В третьем наборе единственная возможная ПСП — ()()()() со стоимостью \(1 + 1 + 1 + 1 = 4\).
В четвертом наборе оптимально сделать \(s\) равной (())(()) со стоимостью \(3 + 1 + 3 + 1 = 8\).