Let be a proper bracketing sequence if it consists only of the characters , , , , , and satisfies at least one of the following three conditions:
is an empty string;
can be represented as \textbf{S} = S_1 + S_2 + S_3 + \ldots + S_n (n > 1), where S_i are non-empty proper bracketing sequences, and the "" sign denotes string concatenation;
can be represented as \textbf{S} = \textbf{\{} + C + \textbf{\}}, \textbf{S} = \textbf{[} + C + \textbf{]}, or \textbf{S} = \textbf{(} + C + \textbf{)}, where is a proper bracketing sequence.
A string is given, consisting only of the characters , , , , , . Determine the minimum number of characters that need to be inserted to make it a proper bracketing sequence.
A single string consisting of at most characters from , , , , , .
Print a single non-negative integer — the answer to the problem.
Example 1
Example 2