Minimum Additions to Make Parentheses Valid

You are given a string s consisting only of characters '(' and ')'. Your task is to determine the minimum number of parentheses that must be added to the string in order to make it valid. A string is considered valid if it meets the following conditions:

• Every opening parenthesis '(' has a corresponding closing parenthesis ')'.
• Parentheses are correctly nested.

Formally, a valid string satisfies the following property in LaTeX format:

\(\text{balance}(s) = 0\), where each '(' contributes +1 and each ')' contributes -1, and the partial sum is never negative.

For example:

• For input "()" the string is already valid so the answer is 0.
• For input "(()" one additional ')' is needed to balance the string, so the answer is 1.

inputFormat

The input contains a single line with a string s composed exclusively of the characters '(' and ')'. It is guaranteed that the length of s does not exceed 10⁵.

outputFormat

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

()

0