Shil is very bad at greedy algorithms. So he decided to practice a lot of greedy problems. He came across a very good problem.Problem is as follows:
Given a linear strip of length N. Strip consists of N cells painted in either BLACK or WHITE color. At each move you can do following process:
- Take any 2 or 3 contiguous cells.
- Invert their colors (i.e replace BLACK cells with WHITE cells and WHITE cells with BLACK cells).
You are required to answer minimum number of moves in which you can change all the cells into same color( either WHITE or BLACK).
Input
First line of input contains N which represents length of strip.
Second line of input consists of string of length N. Each character of string will be W or B . B represents Black cell and W represents White cell.
Output
Minimum number of moves in which you can change all the cells into same color .i.e make the whole strip consisting of cells having same color.
Constraints
2 ≤ N ≤ 20
In the give sample case you can make whole string monochromatic as follows:
Method 1: WWBBBWW to WWWWWWW by performing a move on cells 3 to 5(1-indexed).
Method 2: WWBBBWW to BBBBBWW to BBBBBBB in a total of 2 moves.
Thus minimum number of moves is 1.
