Minimum Parentheses Additions

Given a string s consisting only of the characters ( and ), your task is to determine the minimum number of parentheses that need to be added in order to make s a valid parentheses sequence.

A valid parentheses sequence is defined as follows: every opening parenthesis ( has a corresponding closing parenthesis ), and the pairs of parentheses are properly nested. Mathematically, one common way to validate the sequence is to ensure that if we define a balance variable which increases by 1 when encountering ( and decreases by 1 when encountering ), then the balance never becomes negative and ends at 0. In other words, if at any point the balance b satisfies b < 0, the sequence is invalid.

Your goal is to compute the smallest number of insertions needed such that the modified string is a valid sequence.

The core idea can be described using the following formula:

$$ answer = left\_needed + right\_needed $$

where left_needed is the number of additional ( required and right_needed is the number of additional ) required.

inputFormat

The input is provided via standard input (stdin) and consists of a single line containing a non-empty string s of characters ( and ). You may assume that the length of s is between 0 and 10⁵.

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of parentheses that must be added to make the sequence valid.

## sample

(

1

</p>