Nikita has a line oftiles indexed from to . She wants to paint them to match a color configuration, , which is comprised of colors: and
In one stroke, Nikita can paintor more adjacent tiles a single color. After she finishes painting, each tile( should be painted color .
It should be noted that it is not allowed to apply more thanstroke on a tile.
Given the required color configuration, find and print the minimum number of strokes required for Nikita to paint alltiles.
Note: In a line of tiles,tiles with the indices and are considered adjacent only if .
The first line contains a single integer,
The second line contains a string, , denoting the desired color configuration.
For each characterin :
- If , it means the tile must be painted red.
- If , it means the tile must be painted blue.
Print the minimum number of strokes required to paint alltiles in the desired color configuration.
Sample Input 0
Sample Output 0
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2
Sample Case 0:
Nikita will paint allconsecutive tiles red in a single stroke:
Sample Case 1:
Nikita will needstrokes to paint all tiles: