生物学家发现了一种奇怪的 DNA 分子，它最适合被描述为一个由字符集 $\{A, B\}$ 中的字符组成的长度为 $N$ 的序列。一次不寻常的突变序列导致该 DNA 链最终仅由字符 'A' 组成。生物学家觉得这非常奇特，于是开始更深入地研究这些突变。

他们发现了两种类型的突变：

• 第一种突变会改变序列中的单个字符（$A \to B$ 或 $B \to A$）。
• 第二种突变会改变序列的整个前缀，具体来说，是将位置 $1$ 到 $K$（对于某个满足 $1 \le K \le N$ 的 $K$）的所有字符替换为另一种字符（$A$ 替换为 $B$，$B$ 替换为 $A$）。

计算将初始分子转换为最终状态（仅包含字符 'A'）所需的最少突变次数。突变可以以任何顺序发生。

输入格式

第一行包含一个正整数 $N$（$1 \le N \le 1\,000\,000$），表示分子的长度。

第二行包含一个长度为 $N$ 的字符串，其中每个字符均为 'A' 或 'B'。该字符串表示分子的初始状态。

输出格式

输出唯一的一行，包含所需的最少突变次数。

样例

输入 1

4
ABBA

输出 1

2

输入 2

5
BBABB

输出 2

2

输入 3

12
AAABBBAAABBB

输出 3

4