Nikita has a line of tiles indexed from to . She wants to paint them to match a color configuration, , which is comprised of colors: and .
In one stroke, Nikita can paint or 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 than stroke on a tile.
Given the required color configuration, find and print the minimum number of strokes required for Nikita to paint all tiles.
Note: In a line of tiles, tiles with the indices and are considered adjacent only if .
The first line contains a single integer, , denoting the number of tiles to be painted.
The second line contains a string, , denoting the desired color configuration.
For each character in :
Print the minimum number of strokes required to paint all tiles 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 all consecutive tiles red in a single stroke:
Sample Case 1:
Nikita will need strokes to paint all tiles: