Minimum Parentheses Removal

You are given a string s consisting of parentheses (and possibly other characters). Your task is to determine the minimum number of parentheses that must be removed so that the resulting string is valid. A valid string is one where every opening parenthesis (' has a corresponding closing parenthesis ') in the correct order.

For example:

• s = "()())()" requires the removal of 1 parenthesis.
• s = "((())" requires the removal of 1 parenthesis.
• s = "(()))(()" requires the removal of 2 parentheses.

Your program should read the input string from standard input and output the minimum number of removals to standard output.

inputFormat

The input consists of a single line containing a string s which represents the sequence of characters including parentheses.

Constraints:

• The length of the string is at most 10⁵ characters.

outputFormat

Output a single integer which is the minimum number of parentheses that must be removed to make the string valid.

()())()

1