该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

生物学家希蒙发现了一种奇怪的DNA分子，最好描述为由N个字符组成的序列，字符取自集合{A, B}（只由AB组成）。一个不太可能的变异序列导致了一个只包含A的DNA链。生物学家们觉得这非常奇怪，于是开始更详细地研究这些突变。

他们发现了两种类型的突变。一种类型导致改变序列中的单个字符（A → B 或 B → A）。第二种类型改变了整个序列的前缀，具体地说是用另一个字符（A换成B，B换成A）替换位置从1到K的所有字符（对于某个介于1和N之间的K，包括K）。

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

输入格式

第一行一个整数，表示 $N$。

第二行 $N$ 个字符，表示该序列。

输出格式

一行，一个整数，表示答案。

样例 #1

样例输入 #1

4
ABBA

样例输出 #1

2

样例 #2

样例输入 #2

5
BBABB

样例输出 #2

2

样例 #3

样例输入 #3

12
AAABBBAAABBB

样例输出 #3

4

提示

$1\le N\le 10^{6}$。

序列仅由 'A','B' 构成。