Problem Description

There is a sequence of $N$ letters consisting of $A$ and $B$.

Each operation can be one of two types:

1. Change a character in the sequence ($A$ to $B$ or $B$ to $A$);

2. Change a prefix of the sequence, i.e., perform operation 1 on the characters from $1$ to $K$ where $1 \le K \le N$.

Find the minimum number of operations required to make the entire sequence consist of only $A$s.

Input Format

The first line contains an integer, $N$.

The second line contains $N$ characters, representing the sequence.

Output Format

A single line containing an integer, representing the answer.

Sample Input and Output

Sample Input #1

4
ABBA

Sample Output #1

2

Sample Input #2

5
BBABB

Sample Output #2

2

Sample Input #3

12
AAABBBAAABBB

Sample Output #3

4

Notes

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

The sequence consists only of 'A' and 'B'.

The problem is translated from COCI 2011/2012 #5 T3.

见题面 Input 部分

见题面 Output 部分