== include(page="template/taskheader" task_id="brackets") ==

Erai in camera ta, iti vedeai de treaba ta, treceai Trie-ul persistent in documentatia pentru Finala ACM. Deodata, bate cineva la usa. Vecinul de alaturi te roaga sa-i imprumuti doua parantezari corecte, pentru ca are niste prieteni in vizita si ar vrea sa joace un joc. Te uiti prin camera, vezi un treap rupt in doua sub masa, un FFT cu constanta un milion scrijelit pe oglinda, in final vezi si un sir de paranteze ramas intr-o cutie de pizza.

Erai in camera ta, iti vedeai de treaba ta, treceai Trie-ul persistent in documentatia pentru Finala ACM. Deodata, bate cineva la usa. Vecinul de alaturi te roaga sa-i imprumuti doua parantezari corecte, pentru ca are niste prieteni in vizita si ar vrea sa joace un joc. Fiindca nu are o parere foarte buna despre tine, el iti ofera o definitie recursiva a corectitudinii unui sir de paranteze, in speranta ca o poti urmari:
 
- Sirul "()" este corect.
- Daca sirul $A$ este corect, atunci si sirul $(A)$ este corect.
- Daca sirurile $A$ si $B$ sunt corecte, atunci si sirul $A$ concatenat cu $B$ este corect.
 
Te uiti prin camera, vezi un treap rupt in doua sub masa, un FFT cu constanta un milion scrijelit pe oglinda, in final vezi si un sir de paranteze ramas intr-o cutie de pizza.

Te hotarasti sa partitionezi sirul tau de paranteze (care nu e neaparat corect) in exact doua subsiruri *de lungime cat mai apropiata* (fapt aparent important pentru jocul dubios al vecinului), astfel incat ambele sa fie siruri de paranteze corecte. Vrei sa scapi cu totul de parantezele astea, asa ca nu vei lasa niciuna in cutia de pizza.