Minimum Bracket Addition

Given a string s containing brackets ( and ), return the minimum number of brackets that can be inserted so that the brackets are balanced.

Constraints

• n ≤ 100,000 where n is the length of s

https://binarysearch.com/problems/Minimum-Bracket-Addition

Examples

Example 1

Input

• s = )))((

Output

• answer = 5

Explanation

We can insert ((( to the front and )) to the end

Solution