Type: Default 1000ms 256MiB

括号店老板的微笑

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

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

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

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

合法括号序列定义如下:

  1. 空串是合法括号序列;
  2. 如果 AA 是合法括号序列,那么 (A) 也是合法括号序列;
  3. 如果 AA 和 BB 都是合法括号序列,那么 ABAB 也是合法括号序列。

Format

Input

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

Output

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

Samples

(()))(
2

Note

样例说明:

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

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