eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Вставити дужки

Вставити дужки

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Милхаузу необхідно на завтра вирішити задачу, і їй потрібна Ваша допомога. Ось завдання:

Заданий рядок, що складається з дужок. Необхідно перетворити цей рядок в правильну послідовність, вставляючи якомога меншу кількість дужок в будь-яку позицію (видаляти або змінювати існуючі дужки можна). Правильнною є послідовність, яка задовольняє наступним правилам:

  • Порожня послідовність є правильною.

  • Якщо послідовність s правильна, то (s) також правильна.

  • Якщо послідовності s і t правильні, то їх конкатенація st також правильна дужкова послідовність.

Наприклад, "(()())", "" і "(())()" правильні дужкові послідовності, а "()) (", "() (" і ")" - ні.

Вхідні дані

Задана рядок з дужок, який містить від 1 до 50 символів включно.

Вихідні дані

Вивести найменшу кількість дужок, яку слід вставити, для того щоб вхідна послідовність стала правильною.

Приклад

Вхідні дані #1
(()(()
Вихідні дані #1
2