match

Match

h2. Restrictii si Precizari:

* $2 ≤ N ≤ 1 000 000$

* $2 ≤ N ≤ 100000$

* $Pentru testele în valoare de 10 puncte N ≤ 18.$
* $Pentru testele în valoare de 27 puncte N ≤ 2 000.$
* $Spunem că o secvenţă de paranteze A este mai mică în sens lexicografic decât secvenţa de paranteze B dacă există un indice i, 1 ≤ i ≤ N, astfel încât Aj = Bj pentru fiecare j < i, şi A(i) < B(i).$

table(example). |_. match.in |_. match.out |_. Explicatie |
| abbaaa
| (()())

| O altă secvenţă validă de paranteze este (())(), dar aceasta nu este cea mai mica în sens lexicografic.

| O altă secvenţă validă de paranteze este (())(), dar aceasta nu este cea mai mica în sens lexicografic. |

| abab
| -1
| Nu există nici o secvenţă validă de paranteze, care se potriveşte cu şirul dat.