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 a single character of the sequence (A → B or B → 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.

입력

The first line of input contains the positive integer N (1 ≤ N ≤ 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.

출력

The first and only line of output must contain the required minimum number of mutations.

 

4
ABBA

2

5
BBABB

2

12
AAABBBAAABBB

4