题目描述

给定一个仅由 ( 与 ) 构成的括号序列，请求出最少删去多少括号可以使它变成匹配的。匹配定义如下：

空序列是匹配的；

如果括号序列 s 是匹配的，那么 (s) 也是匹配的；

如果括号序列 s 与 t 是匹配的，那么 st 也是匹配的。

输入格式

单个字符串：表示输入的序列。

输出格式

单个整数：表示最少删去多少个括号才能使输入序列变成匹配的。

()()

0

(()

1

样例2说明

删除一个(

数据规模与约定

设 n 表示输入序列的长度

对于 50% 的数据，1≤n≤1,000； 对于 100% 的数据，1≤n≤1,000,000；