Description

奶牛 Bessie 正试图在她的新笔记本电脑上输入一个平衡的括号字符串，但由于她的蹄子很大，因此非常笨拙，经常输入错误的字符。

请你计算：要使该字符串变为平衡括号字符串，最少需要反转多少个字符。

一次反转可以将一个左括号 ( 变为右括号 )，也可以将一个右括号 ) 变为左括号 (。

一个括号字符串被称为平衡，当且仅当：

• 字符串中的 ( 和 ) 数量相同；
• 对于字符串的任意前缀，( 的数量不少于 ) 的数量。

例如，以下字符串是平衡的：

()
(())
()(()())

以下字符串不是平衡的：

)(
())(
((())))

Format

Input

输入一个只包含 ( 和 ) 的字符串 $s$。

数据范围：

$|s|$ 为偶数。

$2 \le |s| \le 100000$

Output

输出一行一个整数，表示要将该字符串变为平衡括号字符串，最少需要反转的括号数量。

Samples

())(

2

Limitation

1s, 1024KiB for each test case.