Дана строка \(s\) длины \(n\), состоящая из символов \(\texttt{A}\) и \(\texttt{B}\). Вам разрешено выполнять следующую операцию:
- Выбрать индекс \(1 \le i \le n - 1\) такой, что \(s_i = \texttt{A}\) и \(s_{i + 1} = \texttt{B}\), и поменять местами \(s_i\) и \(s_{i+1}\).
Для каждого индекса \(1 \le i \le n - 1\) вам разрешается выполнить данную операцию не более одного раза. Однако вы можете делать это в любом порядке. Найдите максимальное количество операций, которое вы можете выполнить.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное количество операций, которое можно выполнить.
Примечание
В первом наборе входных данных можно выполнить операцию ровно один раз для \(i=1\), так как \(s_1=\texttt{A}\) и \(s_2=\texttt{B}\).
Во втором наборе входных данных можно показать, что для любого индекса выполнить операцию невозможно.
В третьем наборе входных данных можно выполнить операцию с \(i=2\) и получить \(\texttt{ABAB}\). Затем еще одну операцию с \(i=3\), чтобы получить \(\texttt{ABBA}\). И, наконец, еще одну операцию с \(i=1\), чтобы получить \(\texttt{BABA}\). Заметим, что хотя в конце \(s_2 = \texttt{A}\) и \(s_3 = \texttt{B}\), мы не можем повторно выполнить операцию с \(i=2\), так как для каждого индекса операция может быть выполнена не более одного раза.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
AB
4
BBBA
4
AABB
|
1
0
3
|