Game Night#9884
It is finally Bobby's birthday, and all of his Acquaintances, Buddies and Colleagues have gathered for a board game night. They are going to play a game in which players form up to three large teams. Bobby decided to split his guests according to how well he knows them: the Acquaintances form team , the Buddies form team , and the Colleagues form team .
While Bobby was busy explaining the rules, all of his guests had already taken their seats around his large circular living-room table. However, it is crucial for the game that all members of each team sit next to each other. Otherwise, members of other teams could easily eavesdrop on their planning and ruin the game. Therefore, some people may need to change seats.
Bobby wants to start the game as soon as possible, so the seat changes should be made as efficiently as possible. Given the current arrangement around the circular table, determine the minimum number of people who must change seats so that every team sits together.
The first line contains an integer n~(1 \le n \le 10^5) — the number of players (and also the number of seats).
The second line contains a string of length consisting only of the characters , and . It lists the teams of the people sitting around the table, in order.
Print one integer — the minimum number of people who must be asked to change seats so that all teams sit together.
Example 1
Example 2
Example 3
Example 4
Example 5