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$

# | Points | Constraints |
---|---|---|

1 | 6 | $1 \leq n \leq 300$ |

2 | 11 | $300 < n \leq 3 \ 000$ |

3 | 65 | $3 \ 000 < n \leq 50 \ 000$ |

4 | 18 | No other constraints |

## Example

`stdin`

```
10
()()((()))
```

`stdout`

```
14
```

## Explanation

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

- $(1, 2)$
- $(1, 4)$
- $(1, 10)$
- $(3, 4)$
- $(3, 10)$
- $(7, 8)$

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

- $(6, 9)$

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

- $(5, 10)$

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

Therefore, the answer is $14$.