CF653F.Paper task

Alex was programming while Valentina (his toddler daughter) got there and started asking many questions about the round brackets (or parenthesis) in the code. He explained her a bit and when she got it he gave her a task in order to finish his code on time.

For the purpose of this problem we consider only strings consisting of opening and closing round brackets, that is characters '(' and ')'.

The sequence of brackets is called correct if:

1. it's empty;
2. it's a correct sequence of brackets, enclosed in a pair of opening and closing brackets;
3. it's a concatenation of two correct sequences of brackets.

For example, the sequences "()()" and "((()))(())" are correct, while ")(()", "(((((" and "())" are not.

Alex took a piece of paper, wrote a string s consisting of brackets and asked Valentina to count the number of distinct non-empty substrings of s that are correct sequences of brackets. In other words, her task is to count the number of non-empty correct sequences of brackets that occur in a string s as a substring (don't mix up with subsequences).

When Valentina finished the task, Alex noticed he doesn't know the answer. Help him don't loose face in front of Valentina and solve the problem!

亚历克斯正在编程时，他的幼女瓦伦蒂娜走了过来，开始问起代码中圆括号（即小括号）的许多问题。他向她简单解释了一番；当她理解后，他给了她一个任务，以便自己能及时完成代码。

在本题中，我们仅考虑由左括号和右括号（即字符 '(' 和 ')'）组成的字符串。

括号序列被称为正确的，当且仅当满足以下条件之一：

1. 它为空；
2. 它形如 "(A)"，其中 A 是一个正确的括号序列；
3. 它是两个正确括号序列的连接（拼接）。

例如，序列 "()()" 和 "((()))(())" 是正确的，而 ")(("、"(((((" 和 "())" 则不是。

亚历克斯取来一张纸，写下一个由括号组成的字符串 $s$，并让瓦伦蒂娜统计 $s$ 中互不相同且非空的子串中，有多少个是正确的括号序列。换言之，她的任务是统计：在字符串 $s$ 中作为子串（注意：不是子序列）出现的、非空且正确的括号序列的个数（不同子串只计一次）。

当瓦伦蒂娜完成任务后，亚历克斯发现自己并不知道答案。请帮助他，以免在瓦伦蒂娜面前丢脸，解决这个问题！

The first line of the input contains an integer n (1 ≤ n ≤ 500 000) — the length of the string s.

The second line contains a string s of length n consisting of only '(' and ')'.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 500\,000$）——字符串 $s$ 的长度。

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

Print the number of distinct non-empty correct sequences that occur in s as substring.

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

In the first sample, there are 5 distinct substrings we should count: "()", "()()", "()()()", "()()()()" and "()()()()()".

In the second sample, there are 3 distinct substrings we should count: "()", "(())" and "(())()".

在第一个样例中，我们需要统计 5 个不同的子串：“()”、“()()”、“()()()”、“()()()()” 和 “()()()()()”。

在第二个样例中，我们需要统计 3 个不同的子串：“()”、“(())” 和 “(())()”。