RoAlgo Contest #4 (avansati) | gadfadar5

Dude, you still have two lives

Don loves correctly parenthesized strings, your friend Raul loves sequences, and you love number theory. Don asked you to write a problem that meets the quality of the RoAlgo contest problems and to give a solution to this problem. You decided to combine number theory, correctly parenthesized strings, and sequences into a single problem.

A string is called correctly parenthesized if and only if you can insert the characters $+$ and $1$ such that the resulting string represents a correct mathematical expression. For example, $(())$ and $()(())$ are correctly parenthesized strings because $(1+(1+1))$ and $(1+1)+(1+(1+1))$ are correct mathematical expressions, but $(()$ and $())(()$ are not correctly parenthesized strings.

Task

You are given the number $n$ and a string $S$ of characters belonging to the set $\{ \texttt{(}, \texttt{)} \}$ of length $n$.

Find $\displaystyle{\sum_{i=1}^{n} \sum_{j=i}^{n} gcd(i, j) \cdot rbs(i, j)}$

Input data

The first line will contain a single natural number representing the number $n$.

The second line contains a string of $n$ characters representing the string $S$.

Output data

Output a single natural number representing the answer to the task.

Constraints and clarifications

• $1 \leq n \leq 200 \ 000$
• $gcd(i, j)$ is the greatest common divisor of the numbers $i$ and $j$.
• $rbs(i, j)$ is $1$ if the subsequence $s_i \ s_{i+1} \ \dots \ s_j$ is correctly parenthesized, otherwise it is $0$

Example

stdin

10
()()((()))

stdout

14

Explanation

The subsequences with $gcd(i, j) = 1$ are:

1. $(1, 2)$
2. $(1, 4)$
3. $(1, 10)$
4. $(3, 4)$
5. $(3, 10)$
6. $(7, 8)$

The subsequence with $gcd(i, j) = 3$ is:

1. $(6, 9)$

The subsequence with $gcd(i, j) = 5$ is:

1. $(5, 10)$

$6 \cdot 1 + 1 \cdot 3 + 1 \cdot 5 = 14$

Therefore, the answer is $14$.