eolymp
bolt
Try our new interface for solving problems
Məsələlər

Номер по скобочной последовательности

Номер по скобочной последовательности

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Правильной скобочной последовательностью из 2n скобок называется такая последовательность, которая может встречаться в некотором арифметическом выражении. Например, ()()() и (())() являются правильными скобочными последовательностями, а (((()) и (()))( - нет.

Все скобочные последовательности можно упорядочить в лексикографическом порядке, считая, что ( меньше, чем ). Скажем, при n=3 список упорядоченных правильных скобочных последовательностей будет выглядеть так: ((())), (()()), (())(), ()(()), ()()().

В этой задаче требуется найти лексикографический номер по правильной скобочной последовательности (нумерация ведётся с нуля).

Giriş verilənləri

В первой строке дано число n (1n30). Во второй строке дана правильная скобочная последовательность из 2n скобок.

Çıxış verilənləri

Выведите номер правильной скобочной последовательности.

Nümunə

Giriş verilənləri #1
3
(()())
Çıxış verilənləri #1
1