Проблема в том что:
1. Пусть у вас уже есть структура в памяти, которая как-то позволяет вам определить правильность за n*log(n).
2. Вы изменили скобочку ( в самом начале.
3. Теперь у вас уже есть новая последовательность, вы должны изменить свою структуру так, чтобы она отвечала правильно уже о новой последовательности.
4. Но чтобы изменить, вы очевидно должны прости по всем оставшимся справа скобочкам, т.к. измененная скобка изменяет значения скобок справа, но не меняет ничего слева.
5. Чтобы пройти вам нужно время O(n).
6. Таким образом, такой структуры нет :Р
Ловко я вам доказал. Да ?