Minimum Parentheses Removal to Validate Sequence

You are given a string S consisting solely of the characters (' and ')'. Your task is to determine the minimum number of parentheses that need to be removed so that the resulting string is a valid parentheses sequence.

A valid parentheses sequence is defined by the following conditions:

• The number of opening parentheses ( is equal to the number of closing parentheses ).
• For every prefix of the string, the number of opening parentheses is not less than the number of closing parentheses.

This can be formulated mathematically as follows: Let open be the number of unmatched ( and extra be the number of unmatched ) after processing the string. The answer is given by:

[ \text{answer} = \text{open} + \text{extra} ]

Write a program that reads an input string from stdin and outputs the minimum number of removals required to achieve a valid sequence to stdout.

inputFormat

The input consists of a single line containing the string S with only characters (' and ')'.

outputFormat

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

()))((

2