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