Номер по скобочной последовательности
Правильной скобочной последовательностью из 2n скобок называется такая последовательность, которая может встречаться в некотором арифметическом выражении. Например, ()()() и (())() являются правильными скобочными последовательностями, а (((()) и (()))( - нет.
Все скобочные последовательности можно упорядочить в лексикографическом порядке, считая, что ( меньше, чем ). Скажем, при n=3 список упорядоченных правильных скобочных последовательностей будет выглядеть так: ((())),(()()), (())(), ()(()), ()()().
В этой задаче требуется найти лексикографический номер по правильной скобочной последовательности (нумерация ведётся с нуля).
Входные данные
В первой строке дано число n (1 ≤ n ≤ 30). Во второй строке дана правильная скобочная последовательность из 2n скобок.
Выходные данные
Выведите номер правильной скобочной последовательности.