The Postal Owl

Navrhněte datovou strukturu, která si bude pamatovat posloupnost $2n$ levých a pravých závorek a bude umět zpracovávat následující operace:
- zjištění, jestli je posloupnost dobře uzávorkovaná,
- otočení závorky na pozici $i$.

Posloupnost závorek je dobře uzávorkovaná, pokud se levé a pravé závorky dají spárovat (perfektním párováním) tak, že dva páry závorek se buď neprotínají, tedy `...(...)...(...)...`, nebo je jeden pár obsažen v druhém, tedy `...(...(...)...)...`. Např. posloupnost `(()())(())` je dobře uzávorkovaná, ale `(()()))(()` není.

PS: toto je opět úloha typu "chceme datovou strukturu pro určitý problém". Na začátku si můžeme vybudovat potřebnou datovou strukturu (třeba v lineárním čase), ale poté bychom chtěli umět zpracovávat dané operace v čase lepším než lineárním (zde jsou operace dvě: otočení závorky a test, jestli je uzávorkování korektní).