Problem G
DNA
Biologists have discovered a strange DNA molecule, best described as a sequence of $N$ characters from the set $\{ A, B\} $. An unlikely sequence of mutations has resulted in a DNA strand consisting only of $A$’s. Biologists found that very odd, so they began studying the mutations in greater detail.
They discovered two types of mutations. One type results in changing any single character of the sequence ($A \rightarrow B$ or $B \rightarrow A$). The second type changes a whole prefix of the sequence, specifically replacing all characters in positions from $1$ to $K$ (for some $K$ between $1$ and $N$, inclusive) with the other character ($A$ with $B$, $B$ with $A$).
Compute the least possible number of mutations that could convert the starting molecule to its end state (containing only $A$ characters). Mutations can occur in any order.
Input
The first line of input contains the positive integer $N$ ($1 \le N \le 1\, 000\, 000$), the length of the molecule. The second line of input contains a string with $N$ characters, with each character being either $A$ or $B$. This string represents the starting state of the molecule.
Output
The first and only line of output must contain the required minimum number of mutations.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 ABBA |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 BBABB |
2 |
| Sample Input 3 | Sample Output 3 |
|---|---|
12 AAABBBAAABBB |
4 |