Назовём скобочную последовательность идеальной, если она образована некоторым количеством открывающих скобок, за которыми следует такое же количество закрывающих скобок. Глубиной идеальной скобочной последовательности назовём количество скобок какого-то одного вида в ней. Глубиной скобки назовём количество скобок того же вида, включая её саму, до ближайшего к ней края последовательности. Например, последовательность (((()))) имеет глубину 4, а скобки в ней имеют глубины 1, 2, 3, 4, 4, 3, 2 и 1 соответственно.

Очевидно, что любую скобочную последовательность можно преобразовать в идеальную (возможно, пустую), если удалить из неё некоторое количество скобок.

Вам дана скобочная последовательность, возможно, неидеальная. Для каждой скобки в этой последовательности требуется определить две величины:

• максимально возможную глубину данной скобки в идеальной скобочной последовательности, полученной удалением некоторых скобок из исходной последовательности;
• максимально возможную глубину идеальной скобочной последовательности, в которую входит эта скобка; идеальная скобочная последовательность получается удалением некоторых скобок из исходной последовательности.

Если какая-то скобка не входит ни в какую идеальную скобочную последовательность, которую можно было бы получить удалением некоторых скобок из исходной последовательности, обе величины будем считать равными 0.