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