Minimum Removals for Valid Parentheses

You are given a string s consisting solely of the characters '(' and ')'. Your task is to determine the minimum number of characters to remove from the string so that the remaining string forms a valid parentheses sequence.

A valid parentheses sequence is defined such that every opening parenthesis '(' has a corresponding closing parenthesis ')'. In other words, if we denote the number of unmatched opening and closing parentheses by \(\text{open_count}\) and \(\text{close_count}\) respectively, then the answer is:

\[ \text{result} = \text{open_count} + \text{close_count} \]

For example, given the input string "(()())((", there are two extra '(' characters that remain unmatched, so the minimum removals required is 2.

inputFormat

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

outputFormat

Output a single integer, which is the minimum number of removals required to make the string a valid parentheses sequence.

## sample

(()())

0