题目描述

粉刷匠接到了一个新任务，有一堵很长很长的墙，长度为偶数，每个单位长度上有一个括号，为(或)。而现在他需要将整堵墙的括号变为一个合法的匹配。请帮助他计算至少需要修改多少个括号（例如，将左括号更改为右括号，反之亦然），使得括号满足合法匹配。

有几种方法可以定义一串括号“匹配”的含义。最简单的定义可以是：(和) 的总数必须相同，并且对于字符串的任何前缀，(的数量都不少于)的数量。例如，下列字符串都是平衡的：

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

而这些不是：

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

输入格式

第 1 行：一串偶数长度的括号，最多 100,000 个字符。

输出格式

第 1 行：一个整数，给出必须切换以将字符串转换为平衡字符串的最小括号数。

样例输入1

())(

样例输出1

2

样例输入2

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

样例输出2

4

数据范围

【输入输出样例1解释】

最后一个括号必须切换，两个中间右括号之一也必须切换。

【数据范围与约定】

对 $25\%$ 的数据，括号长度不超过 $100$，

对 $100\%$ 的数据，括号长度为偶数，不超过 $10^5$ 个字符。