Problem Description

There are two coal mines, each employing a group of miners. Coal mining is arduous, so miners require good nutrition. Whenever a food truck arrives at a coal mine, the miners produce a certain amount of coal.

There are three types of food trucks: meat trucks, fish trucks, and bread trucks. Miners enjoy varied diets. If the provided food is constantly changing, their coal production will increase. Whenever a new food truck arrives at a coal mine, the miners compare this new food with the previous two (or fewer, if there have been less than two previous deliveries) and:

• If these deliveries are all of the same type, the miners produce one unit of coal.
• If these deliveries include two different types of food, the miners produce two units of coal.
• If these deliveries include three different types of food, the miners produce three units of coal.

The types and order of food truck deliveries are known in advance. Determining which truck goes to which mine can influence coal production. Food trucks cannot be split; each must be sent entirely to one or the other mine. The two mines do not require the same number of food trucks (in fact, it is permissible to send all trucks to one mine).

Given the types and order of food truck deliveries, you are required to write a program that determines which truck should be sent to mine 1 and which to mine 2 to maximize the total coal production of both mines.

Input Format

The first line of input contains an integer \( N (1 \leq N \leq 100,000) \), representing the number of food trucks.

The second line contains a string of \( N \) characters, indicating the types of food in the order of delivery. Each character is one of three uppercase letters: M (meat), F (fish), or B (bread).

Output Format

Output a single integer, representing the maximum total coal production.

Sample Input and Output

Sample Input #1

6
MBMFFB

Sample Output #1

12

Sample Input #2

16
MMBMBBBBMMMMMBMB

Sample Output #2

29

Notes

In Sample 1, food trucks can be delivered in the following order: mine 1, mine 1, mine 2, mine 2, mine 1, mine 2, producing coal amounts of 1, 2, 1, 2, 3, and 3 units, totaling 12 units.

Other delivery methods can also achieve this maximum total coal production.

见题面 Input 部分

见题面 Output 部分