636. Minimum Insertions to Balance Parentheses

In this variant a valid string requires every '(' to be matched by two consecutive ')'. Given a string s of '(' and ')', return the minimum number of insertions (of '(' or ')') to make it valid. The input is JSON {s}.

Input: JSON {s}.

Output: Integer — the minimum insertions needed.

Examples

Input: {"s":"(()))"}
Output: 1
Explanation: One insertion balances it.

Input: {"s":"())"}
Output: 0
Explanation: One '(' with two ')' is valid.

Input: {"s":"))())("}
Output: 3
Explanation: Three insertions needed.

Constraints

• 0<=|s|<=10^5

Asked by