Bessie пытается набрать сбалансированную скобочную строку на новом ноутбуке, но большие копыта делают её неуклюжей и она ошибается. Найдите минимальное число символов, которые нужно перевернуть (открывающую скобку в закрывающую или наоборот), чтобы строка стала сбалансированной.

Есть несколько определений баланса. Самое простое: общее число открывающих и закрывающих скобок одинаково, а в любом префиксе открывающих не меньше закрывающих. Например, следующие строки сбалансированы:

()
(())
()(()())

Следующие — нет:

)(
())(
((())))

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

• Строка 1: скобочная строка $A$ чётной длины не более 100,000 символов.

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

• Строка 1: одно целое число, минимум скобок для переворота, чтобы получить сбалансированную строку.

Примеры

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

())(

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

2

Примечание

Нужно перевернуть последнюю скобку и одну из двух средних закрывающих.

Автор задачи: Brian Dean, 2012