亚历克斯正在编程,而瓦伦蒂娜(他蹒跚学步的女儿)到达那里并开始询问有关代码中圆括号(或圆括号)的许多问题。他向她解释了一些,当她明白后,他给了她一项任务,以便按时完成他的代码。
出于此问题的目的,我们仅考虑由左右圆括号组成的字符串,即字符“(”和“)”。
如果满足以下条件,则括号序列被称为正确:
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 个不同的子字符串:“()”、“(())”和“(())()”。