У пользователя ainta есть стек, в котором содержатся n красных и синих шариков. Он умеет выполнять со стеком операцию, которая изменяет цвета шаров в стеке. Операция описывается алгоритмом:
Если в стеке нет синих шариков, ainta не сможет выполнить описанную операцию. По заданному изначальному состоянию стека, ainta хочет узнать, какое наибольшее количество операций он может выполнить одну за другой. Помогите ему, посчитайте это значение.
В первой строке записано целое число n (1 ≤ n ≤ 50) — количество шариков в стеке.
Во второй строке записана последовательность s (|s| = n), описывающая изначальное состояние стека: i-й символ в строке s обозначает цвет i-го шарика (считайте, что шарики в стеке пронумерованы, начиная от вершины стека). Если символ равняется "R", то шарик красный. Если символ равняется "B", то шарик синий.
Выведите максимальное количество операций, которые ainta может последовательно выполнить.
Пожалуйста, не используйте спецификатор %lld для чтения и записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
3
RBR
2
4
RBBR
6
5
RBBRR
6
Описание первого тестового примера.
Вот как пользователь ainta выполняет первую операцию. Он вытаскивает один красный шарик, меняет шарик в центре с синего на красный и добавляет в стек один синий шарик.
Вот как пользователь ainta выполняет вторую операцию. Так как на вершине стека синий шар, он не будет вытаскивать красные шары. Он просто меняет верхний шар с синего на красный.
Теперь ainta больше не может применить ни одной операции, поскольку в стеке не осталось синих шаров. ainta выполнил две операции, так что ответ равняется 2.
Описание второго примера приведено ниже. Синяя стрелка обозначает применение одной операции.
| Codeforces Round 233 (Div. 2) |
|---|
| Закончено |
