You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

具体问题是：给定长度为N(1 <= N <= 50,000)的只包含左右（小）括号的字符串。能否找出相邻的两个左括号，和两个相邻的右括号，并且左括号的位置比右括号的位置靠左。

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

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

1. )((()())())

2. )((()())())

3. )((()())())

4. )((()())())

输入格式

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

输出格式

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

样例数据

input

)((()())())

output

4

数据规模与约定

30%数据保证 N<=222.

50%数据保证 N<=2222

100%数据如题目描述。

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

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