Minimum Insertions to Balance a Parentheses String

Only insertions of left and right parentheses are allowed, to turn the string into an ordinary valid parenthesis string. Each left parenthesis is matched with one right parenthesis. Find the minimum number of insertions.

输入格式

One line containing a string of only left and right parentheses, of length 1..100000.

输出格式

Output one integer, the answer.

样例 1

输入：

()))

输出：

2

样例 2

输入：

(()))

输出：

1

样例 3

输入：

))((

输出：

4

样例说明

The examples give 2, 1 and 4 respectively. The 4 in the original second example actually belongs to a different string; this site corrects it according to the statement body and the explanation.