Băi băiatule, mai ai două vieți

Don-ul iubește șirurile corect parantezate, prietenul tău Raul iubește secvențele, iar tu iubești teoria numerelor. Don-ul te-a rugat să scrii o problemă care să satisfacă calitatea problemelor concursului RoAlgo și să îi dai o soluție la această problemă. Ai decis să combini teoria numerelor, șirurile corect parantezate și secvențele într-o singură problemă.

Un șir se numește corect parantezat dacă și numai dacă se pot introduce caracterele $+$ și $1$ astfel încât șirul obținut să reprezinte o expresie matematică corectă. De exemplu $(())$ și $()(())$ sunt șiruri corect parantezate deoarece $(1+(1+1))$ și $(1+1)+(1+(1+1))$ sunt o expresii matematice corecte, dar $(()$ și $())(()$ nu sunt șiruri corect parantezate.

Cerință

Tu ai scris numărul $n$ și un șir $S$ de caractere aparținând mulțimii $\{ \texttt{(}, \texttt{)} \}$ de lungime $n$.

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

Date de intrare

Pe prima linie va conține un singur numărul natural reprezentând numărul $n$.

Pe a doua linie se află un șir de $n$ caractere reprezentând șirul $S$.

Date de ieșire

Se afișează un singur număr natural reprezentând răspunsul la cerință

Restricții și precizări

• $1 \leq n \leq 200 \ 000$
• $gcd(i, j)$ este cel mai mare divizor comun al numerelor $i$ și $j$.
• $rbs(i, j)$ este $1$ dacă subsecvența $s_i \ s_{i+1} \ \dots \ s_j$ este corect parantezată, altfel este $0$

Exemplu

stdin

10
()()((()))

stdout

14

Explicație

Subsecvențele cu $gcd(i, j) = 1$ sunt:

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

Subsecvența cu $gcd(i, j) = 3$ este:

1. $(6, 9)$

Subsecvența cu $gcd(i, j) = 5$ este:

1. $(5, 10)$

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

Deci răspunsul este $14$.