CF653F Paper task

Alex 在编程的时候，他的女儿 Valentina（一个小孩）来到身边，不停地问代码中的圆括号（即小括号）的问题。他耐心地给她解释了一些，在她理解后，Alex 给了她一个任务，这样他才能有时间完成自己的代码。 在本题中，我们只关注由左括号 '(' 和右括号 ')' 组成的字符串。 如果一个括号序列满足以下条件之一，则称其为“合法括号序列”： 1. 该序列为空； 2. 该序列是一个被一对括号包裹起来的合法括号序列； 3. 该序列是两个合法括号序列的连接。 例如，序列 "()()" 和 "((()))(())" 是合法的，而 ")(()"、"(((((" 和 "())" 都不是。 Alex 在一张纸上写下了一个只包含括号的字符串 $s$，让 Valentina 统计 $s$ 的所有不同的非空子串中，属于合法括号序列的个数。换句话说，她的任务是统计在字符串 $s$ 中作为子串出现的所有不同的非空合法括号序列的数量（注意是子串，不要与子序列混淆）。 当 Valentina 完成任务后，Alex 发现自己其实并不知道答案。请你帮助 Alex，不要在女儿面前出丑，求出答案。

输入的第一行包含一个整数 $n$（$1 \leq n \leq 500000$），表示字符串 $s$ 的长度。 输入的第二行是一个长度为 $n$ 的字符串 $s$，只包含字符 '(' 和 ')'。

输出一个整数，表示 $s$ 中作为子串出现的所有不同的非空合法括号序列的数量。

在第一个样例中，需要统计的不同子串有 $5$ 个，分别是："()"、"()()"、"()()()"、"()()()()" 和 "()()()()()"。 在第二个样例中，需要统计的不同子串有 $3$ 个，分别是："()"、"(())" 和 "(())()"。 由 ChatGPT 5 翻译