题目描述

有一个由 $A,B$ 组成的 $N$ 个字母的序列。

每次操作可以有两种情况：

1. 改变序列中的一个字符 （$A\to B$ 或 $B\to A$）；

2. 改变序列的前缀，即对 $1$ 到 $K(1\le K\le N)$ 的字符进行操作 1。

求最少进行多少次操作可以使序列全部为 $A$。

输入格式

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

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

输出格式

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

4
ABBA

2

5
BBABB

2

12
AAABBBAAABBB

4

提示

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

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

题目译自 COCI 2011/2012 #5 T3。