该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

括号店老板卖两种括号：左括号 $\texttt{(}$ 和右括号 $\texttt{)}$。

一天，他收到一个只包含括号的字符串 $s$。老板看完后沉默了，因为这个字符串不一定是合法括号序列。

老板可以在字符串的任意位置插入任意数量的括号。请问至少需要插入多少个括号，才能使整个字符串变成一个合法括号序列？

合法括号序列定义如下：

1. 空串是合法括号序列；
2. 如果 $A$ 是合法括号序列，那么 (A) 也是合法括号序列；
3. 如果 $A$ 和 $B$ 都是合法括号序列，那么 $AB$ 也是合法括号序列。

Format

Input

第一行一个字符串 $s(1 \le |s| \le 2 \times 10^5)$，仅由 $\texttt{(}$ 和 $\texttt{)}$ 组成。

Output

输出一行一个整数，表示最少需要插入的括号数量。

Samples

(()))(

2

Note

样例说明：

可以在第一个字符前插入一个 $\texttt{(}$ 来匹配多出来的 $\texttt{)}$，并在末尾插入一个 $\texttt{)}$ 来匹配最后的 $\texttt{(}$。

一种合法结果为：$\texttt{((()))()}$。当然，老板并不关心你插在哪里，他只关心你少买点，哦不，少插点。