Description

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

Each operation can be one of the following two types:

1. Change one character in the sequence ($A\to B$ or $B\to A$).

2. Change a prefix of the sequence, i.e. perform operation 1 on characters $1$ through $K$ $(1\le K\le N)$.

Find the minimum number of operations needed to make the entire sequence all $A$.

Input Format

The first line contains an integer $N$.

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

Output Format

Output one line containing one integer, representing the answer.

4
ABBA

2

5
BBABB

2

12
AAABBBAAABBB

4

Hint

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

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

Translated from COCI 2011/2012 #5 T3.

Translated by ChatGPT 5