Маші необхідно на завтра вирішити задачу, і їй потрібна Ваша допомога. Ось завдання:
Заданий рядок, що складається з дужок. Необхідно перетворити цей рядок в правильну послідовність, вставляючи якомога меншу кількість дужок в будь-яку позицію (видаляти або змінювати існуючі дужки можна). Правильною є послідовність, яка задовольняє наступним правилам:
Порожня послідовність є правильною.
Якщо послідовність s є правильною, то \((s)\) також правильна послідовність.
Якщо дві послідовності \(s\) і \(t \) правильні, то їх конкатенація \(st\) також правильна дужкова послідовність.
Наприклад, "(()())", "" і "(())()" правильні рядки, а "()) (", "() (" і ")" - ні.
Формат вхідних даних
Заданий рядок з дужок, який містить від 1 до 50 символів включно.
Формат вихідних даних
Вивести найменшу кількість дужок, яку слід вставити, для того щоб вхідний рядок став правильною дужковою послідовністю.
Приклад вхідних даних
(()(()
Приклад вихідних даних
2
Коментарі