swap

O parantezare corectă se obține aplicând una dintre următoarele reguli:

• șirul vid este o parantezare corectă;
• dacă $S$ este o parantezare corectă, atunci (S) este o parantezare corectă, iar cele două paranteze ( și ) care încadrează șirul S sunt denumite paranteze pereche;
• dacă $S_1$, $S_2$, $\dots$, $S_k$ sunt parantezări corecte atunci șirul $S_1 \ S_2 \ \dots \ S_k$ obținut prin concatenarea acestora este o parantezare corectă.

De exemplu șirurile (), ()(), (()) și (()())() reprezintă parantezări corecte, în timp ce )(, ()()( și (()()))) nu sunt parantezări corecte.
Fie $S$ un șir care reprezintă o parantezare corectă. Pentru fiecare dintre parantezele pereche din șirul $S$ asociem un cost egal cu diferența dintre poziția pe care se află în $S$ paranteza închisă și poziția parantezei deschise pereche. Pozițiile în șir le considerăm numerotate începând cu $1$. Costul total al unei parantezări corecte îl reprezintă suma costurilor tuturor parantezelor pereche din aceasta.
De exemplu, șirul (()()) este format din trei paranteze pereche, situate pe pozițiile $2$ și $3$, apoi $4$ și $5$, respectiv $1$ și $6$. Costul total al parantezării este $3$ - $2$ + $5$ - $4$ + $6$ - $1$ = $7$.
Numim operație swap interschimbarea a două paranteze situate în șir pe poziții alăturate. Această operație este validă doar dacă șirul nou obținut este la rândul său o parantezare corectă și dacă noua parantezare are costul total strict mai mic decât cea inițială.

Cerință

Scrieți un program care citește o succesiune de $N$ caractere reprezentând o parantezare corectă și determină:

1. Costul total asociat parantezării citite;
2. Costul minim al unei parantezări obținute prin efectuarea unei singure operații swap valide asupra parantezării citite;
3. Numărul de posibilități de a efectua o singură operație swap validă asupra parantezării inițiale pentru a obține costul determinat conform cerinței 2.

Date de intrare

Fișierul de intrare swap.in conține pe prima linie numărul natural $N$ și pe a doua linie o succesiune de $N$ caractere reprezentând o parantezare corectă.

Date de ieșire

În fișierul de ieșire swap.out va conține pe prima linie un număr natural reprezentând costul parantezării citite. A doua linie va conține un număr natural reprezentând costul minim determinat conform cerinței 2 sau valoarea $-1$ când nu se poate efectua nici o operație swap validă asupra parantezării citite. A treia linie a fișierului va conține un număr natural reprezentând răspunsul la cerința 3 sau $0$ dacă numărul afișat conform cerinței 2 a fost $-1$.

Restricții și precizări

• $2 \leq N \leq 90 \ 000$;
• Pe fiecare dintre cele $3$ linii ale fișierului de ieșire trebuie să se afle un singur număr întreg. Dacă numărul de pe prima linie este corect, se acordă $20$% din punctajul testului. Dacă numărul de pe a doua linie este corect, se acordă $20$% din punctaj. Dacă numărul de pe a treia linie este corect, se acordă $60$% din punctaj.

Exemplu

swap.in

8 
()(())()

swap.out

6
4
1

Explicație

Pentru cerința 1 costul parantezării este $2 - 1 + 6 - 3 + 5 - 4 + 8 - 7 = 6$. Executând o operație swap între parantezele de pe pozițiile $4$ și $5$ se obține șirul ()()()() care are costul $4$, aceasta fiind singura posibilitate de a obține acest cost.