← 返回题目列表

Codeforces · 653/F

F. 论文任务

中文机器翻译题面 查看原题

亚历克斯正在编程,而瓦伦蒂娜(他蹒跚学步的女儿)到达那里并开始询问有关代码中圆括号(或圆括号)的许多问题。他向她解释了一些,当她明白后,他给了她一项任务,以便按时完成他的代码。

出于此问题的目的,我们仅考虑由左右圆括号组成的字符串,即字符“(”和“)”。

如果满足以下条件,则括号序列被称为正确:

1.它是空的;
2. 这是正确的括号顺序,包含在一对左括号和右括号内;
3. 它是两个正确的括号序列的串联。

例如,序列“()()”和“((()))(())”是正确的,而“)(()”、“(((((”和“())”则不正确。

Alex 拿了一张纸,写了一个由括号组成的字符串 s,并要求 Valentina 计算 s 中正确的括号序列的不同非空子串的数量。换句话说,她的任务是计算字符串 s 中作为子串出现的非空正确括号序列的数量(不要与子序列混淆)。

当瓦伦蒂娜完成任务时,亚历克斯注意到他不知道答案。帮助他不要在瓦伦蒂娜面前丢脸,解决问题!

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 500 000) - 字符串 s 的长度。

第二行包含长度为 n 的字符串 s,仅由 '(' 和 ')' 组成。

输出

打印 s 中出现的不同非空正确序列的数量作为子字符串。

示例

输入 #1

10
()()()()()

输出 #1

5

输入 #2

7
)(())()

输出 #2

3

注意

在第一个示例中,我们应该计算 5 个不同的子字符串:“()”、“()()”、“()()()”、“()()()()”和“()()()()()”。

在第二个示例中,我们应该计算 3 个不同的子字符串:“()”、“(())”和“(())()”。