题目描述

​ 在学习括号匹配的时候，凯南在思考一个无聊的问题：能否找出双括号匹配的对数。

​ 具体问题是：给定长度为N(1 <= N <= 50,000)的只包含左右（小）括号的字符串。

我们定义：相邻的两个左括号，和两个相邻的右括号，并且左括号的位置比右括号的位置靠左为一个 匹配。

​ 当然这些两个左右括号很多，最终的问题是：能否找出有多少对不同的连续左右括号对。

​ 例如：给定括号序列 )((()())())，有四对不同的括号对匹配，具体如下，你不必考虑括号匹配的就近原则，只要考虑左括号在右括号左边即可。

)((()())())

 ^^   ^^

 )((()())())

   ^^  ^^

 )((()())())

  ^^      ^^

 )((()())())

   ^^     ^^

输入格式

一个字符串，保证只包含左右小括号。字符串长度为N（1 <= N <= 50,000)

输出格式

一个整数，表示匹配的左右括号对。

样例

input

)((()())())

output

4

限制与提示

30%数据保证 N<=222.

50%数据保证 N<=2222

100%数据如题目描述。

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$