Теперь, когда Курони исполнилось 10 лет, он большой мальчик и больше не любит массивы целых чисел в качестве подарков. В этом году он хочет получить скобочную последовательность в качестве подарка на день рождения. В частности, он хочет, чтобы последовательность скобок была настолько сложной, что, как бы он ни старался, он не сможет удалить простую подпоследовательность!

Назовем строку, образованную $$$n$$$ символами '(' или ')' простой, если ее длина $$$n$$$ четна и положительная, ее первые $$$\frac{n}{2}$$$ символов  — это '(', а ее последние $$$\frac{n}{2}$$$ символов  — это ')'. Например, строки () и (()) являются простыми, в то время как строки )( и ()() не являются простыми.

Курони будет дана строка, образованная символами '(' и ')' (заданная строка не обязательно является простой). Операция состоит из выбора подпоследовательности символов строки, которая образует простую строку, и удаления всех символов этой подпоследовательности из строки. Заметьте, символы подпоследовательности не обязаны идти подряд. К примеру, он может применить операцию к строке ')()(()))', выбрать подпоследовательность из выделенных жирным шрифтом символов, так как они формируют простую строку '(())', удалить эти символы с строки и получить '))()'.

Курони должен выполнить минимально возможное количество операций над строкой таким образом, чтобы с оставшейся строкой больше нельзя было выполнить ни одной операции. Результирующая строка не обязана быть пустой.

Поскольку заданная строка слишком велика, Курони не может понять, как минимизировать количество операций. Можете ли вы помочь ему сделать это?

Последовательность символов $$$a$$$ является подпоследовательностью строки $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов.