Fewest Brackets To Balance

MediumStringGreedyStackParentheses6 hidden tests

You are given a string of only the characters ( and ). You may insert single brackets (either ( or )) at any positions. Find the minimum number of insertions needed to make the whole string valid (every bracket matched and properly nested).

Input format

A single line: a string of ( and ) characters (possibly empty).

Output format

A single integer: the minimum number of bracket insertions required.

Constraints

0 <= length of the string <= 100000

Examples

Example 1

Input

(()

Expected

Explanation

There is one unmatched '('; inserting a single ')' at the end makes "(())" valid, so the answer is 1.

Example 2

Input

))(

Expected

Explanation

Two ')' have no opener and one '(' has no closer; three insertions are needed, so the answer is 3.

Ready to solve this?

Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.

Sign in to solve →