题目描述

小迪最近对仅由 ( 和 ) 组成的字符串很感兴趣。对于一个这样的字符串，小迪会从左到右依次查看每一个括号：

• 如果遇到左括号 (，不做任何操作；
• 如果遇到右括号 )，会往前找到第一个还没用过的左括号跟这个右括号匹配，并标记该左括号为用过；若没有找到能匹配的左括号，则忽略这个右括号继续查看后续括号。

小迪认为该字符串的幸运分数为按上述匹配方法能匹配的括号对数，请你帮他计算这个字符串的幸运分数。

输入格式

输入一行，包含一个仅由 ( 和 ) 组成的字符串，字符串长度不超过 10^5。

输出格式

输出一行，包含一个整数，表示这个字符串的幸运分数。

样例输入

((()

样例输出

1