题目描述

Bob 最近对序列变换特别感兴趣，于是老师给他出了一道题。

给定一个长度为 $n$ 由字符 $A$ 和 $B$ 构成，每次操作可以有两种情况：

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' 构成。

$subtask1$: $N \leq 20$, $20$ 分

$subtask2$: $N \leq 10^3$，$30$ 分

$subtask3$: $1\le N\le 10^{6}$, $50$ 分