Minimum Add to Make Parentheses Valid

Stack
Greedy

Given a string s of '(' and ')' characters, return the minimum number of brackets you need to add to make the string valid.

Examples

Example 1

Input

s

(

)

Output

1

Example 2

Input

s

(

Output

3

Constraints

1 ≤ s.length ≤ 10⁵
s[i] is either '(' or ')'.

Stuck? Hint 1

Track a running balance: +1 per (, -1 per ). A balance that goes negative is a ) needing a partner.

Input

(

)

Expected Output

Ctrl / ⌘ + Enter

Minimum Add to Make Parentheses Valid

Stack
Greedy

Given a string s of '(' and ')' characters, return the minimum number of brackets you need to add to make the string valid.

Examples

Example 1

Input

s

(

)

Output

1

Example 2

Input

s

(

Output

3

Constraints

1 ≤ s.length ≤ 10⁵
s[i] is either '(' or ')'.

Stuck? Hint 1

Track a running balance: +1 per (, -1 per ). A balance that goes negative is a ) needing a partner.

Input

(

)

Expected Output

Ctrl / ⌘ + Enter