题目描述

奶牛Bessie逃跑了，躲在一片长满高草的岭上。农夫约翰试图爬行穿过草地接近Bessie，但难以发现她的踪迹。他面前的草地看起来像一串长度为N（1 ≤ N ≤ 50,000）的括号，例如：)((()())())。

约翰知道：

• Bessie的后腿看起来像两个相邻的左括号((
• 前腿看起来像两个相邻的右括号))
• Bessie的位置可以描述为一对索引x < y，其中x处有((，y处有))

请计算Bessie可能站立的不同位置数量（即满足条件的(x,y)对数）。

输入格式

一行：一个长度为N的括号字符串

输出格式

一行：可能的(x,y)对数

输入输出样例

输入 #1

)((()())())

输出 #1

4

样例解释

在样例字符串中，有4个可能的Bessie位置：

1. 第2-3位((和第6-7位))
2. 第3-4位((和第7-8位))
3. 第3-4位((和第10-11位))
4. 第2-3位((和第10-11位))

每个位置对应一对((和))的出现位置，且((的位置索引小于))的位置索引。