464. Minimum Addition to Make Parentheses Valid

0

Medium

A string of parentheses is considered valid if and only if:
* It is an empty string.
* It can be written as AB, where A and B are valid strings.
* It can be written as (A), where A is a valid string.
You are given a string s consisting of parentheses. In each move, you can insert a parenthesis at any position within the string. Return the minimum number of moves required to make s a valid string.

Input Format

A single line consisting of a string of parentheses.

Output Format

An integer indicating the minimum number of parentheses to be added.

Example

Input

()))()

Output

2

Constraints

1 <= N <= 10^4

Loading...

View Submissions

Console