题目描述

小蓝正在玩一个叫“一维消消乐”的游戏。游戏初始时给出一个长度为 $n$ 的字符串 $S = S_0S_1\ldots S_{n-1}$，字符串只包含字符 $\text{A}$ 和 $\text{B}$。小蓝可以对这个字符串进行若干次操作，每次操作可以选择两个下标 $i, j \in [0, n-1]$，如果 $i < j$ 且 $S_i = \text{A}$ 且 $S_j = \text{B}$，小蓝就可以把它们同时消掉。小蓝想知道在经过若干次操作后，直到无法对字符串继续进行操作时，字符串最多剩下多少个字符。

输入格式

输入一行包含一个长度为 $n$ 的字符串 $S$。

输出格式

输出一行包含一个整数表示答案。

BABAABBA

4

解释 #1

先消掉 $(S_1, S_6)$，再消掉 $(S_4, S_5)$，此时剩下 $\text{BBAA}$，无法继续进行操作。

数据范围

• 对于 $10\%$ 的评测用例，$1 \leq n \leq 20$；
• 对于 $20\%$ 的评测用例，$1 \leq n \leq 100$；
• 对于 $50\%$ 的评测用例，$1 \leq n \leq 10000$；
• 对于所有评测用例，$1 \leq n \leq 10^6$。