括号欠账

题目描述

字符串只含左右圆括号。可以在任意位置插入括号，不能删除或移动原字符。要求从左到右任意前缀左括号数不少于右括号，且全串两者相等。求最少插入数。

输入格式

输入一个非空括号串。

输出格式

输出最少插入次数。

样例 1

输入

())(

输出

2

说明

需为多出的右括号补一个左括号，末尾左括号再补一个右括号。

样例 2

输入

()()

输出

0

说明

已符合两条规则。

数据范围

• 每个串长度1至2000，不含空白字符。
• 仅含左圆括号与右圆括号。