Minimum Parentheses Reversal for Balanced Strings

Bessie the cow is trying to type a balanced string of parentheses on her new laptop, but her large hooves cause her to mis-type some of the characters. In this problem, you are given an even-length string consisting solely of the characters '(' and ')'. Your task is to determine the minimum number of characters that must be reversed (i.e., changing a '(' to a ')' or vice versa) so that the string becomes balanced.

A string of parentheses is considered balanced if:

• The total number of '(' is equal to the total number of ')'.
• For every prefix of the string, the number of '(' is at least as many as the number of ')'.

For example, the following strings are balanced:

• ()
• (())
• ()(()())

While these strings are not balanced:

• ) (
• ())(
• ((())))

inputFormat

The input consists of a single line that contains an even-length string of parentheses.

outputFormat

Output a single integer representing the minimum number of reversals required to make the string balanced.

sample

)(

2