e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Задачи

Вставить скобки

Вставить скобки

Милхаузу необходимо на завтра решить задачу, и ему нужна Ваша помощь. Вот задача:

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

  • Пустая строка правильная.
  • Если s правильная, то (s) также правильная.
  • Если s и t правильные, то их конкатенация st правильная.

Например, "(()())", "" и "(())()" правильные строки, а "())(", "()(" и ")" - нет.

Входные данные

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

Выходные данные

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
(()(()
Выходные данные #1
2