Minimum Parentheses Removal for Validity

You are given a string s consisting only of the characters (' and ')'. Your task is to determine the minimum number of parentheses that must be removed to make the string valid.

A valid string is defined as one where every opening parenthesis has a corresponding closing parenthesis in the correct order. Formally, let \( s = s_1 s_2 \dots s_n \) be the input string. We want to remove the minimum number of characters such that the resulting string \( s' \) satisfies the following:

• The number of \( '(' \) equals the number of \( ')' \).
• In every prefix of \( s' \), the number of \( '(' \) is at least the number of \( ')' \).

For example, for the string "(()())", no removals are necessary, whereas for ")())(()))" at least 2 removals are needed.

inputFormat

The input consists of a single line containing a non-empty string s composed only of characters '(' and ')'.

outputFormat

Output a single integer representing the minimum number of parentheses to remove to make s valid.

(()())

0