括号修复

题目描述

33DAI 的日记本上有一串只由 ( 和 ) 组成的字符，他怀疑这串字符被人改坏了： 现在它已经不是一个合法的括号序列。33DAI 每次可以删掉其中一个字符。

合法括号序列的定义是：

• 空串是合法的；
• 如果 $A$ 合法，那么 ( + $A$ + ) 合法；
• 如果 $A, B$ 都合法，那么 $AB$ 合法。

请你帮他算出，最少删掉几个字符，才能让剩下的字符串是合法括号序列。

输入格式

一行一个字符串 $s$，只包含 ( 和 )。

输出格式

输出一个整数，表示最少需要删掉的字符数。

()(

1

样例 1 解释

删掉最后一个 (，剩下的 () 是合法括号序列。

)(

2

样例 2 解释

两个字符都删掉，剩下空串，空串是合法的。

数据范围

对于所有测试数据，保证 $1 \le |s| \le 10^5$。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。