We’re preparing your current view and syncing the latest data.
Given a string representing colors of gift packages stacked in a row, you want to repaint some prefixes of this sequence so that no two adjacent packages have the same color. The repaint operation allows changing the color of all packages in a prefix to a single color. Determine the minimum number of repaint operations needed to achieve this condition, and output this number.
You must ensure that after performing the repaint operations (possibly zero), no two consecutive packages have the same color.
The first line contains an integer n (1 ≤ n ≤ 100 000), the number of gift packages. The second line contains a string s of length n consisting of uppercase English letters representing the colors of the gift packages.
Output a single integer, the minimum number of repaint operations needed so that no two adjacent packages have the same color.
1 ≤ n ≤ 100 000 s consists of uppercase English letters only.
Example 1
Input
6 ABAABB
Output
2
Explanation
One optimal way is to repaint the prefix ending at position 4 to break the consecutive 'AA', and then repaint the prefix ending at position 6 to change the last two 'B's so no two adjacent packages match.