Description

There are two coal mines, each employing a group of miners. Mining is hard work, so the miners need good meals. Whenever a food truck arrives at a mine, the miners produce some amount of coal.

There are three types of food trucks: meat truck, fish truck, and bread truck. Miners like variety in their meals. If the food keeps changing, their coal output increases. Whenever a new food truck arrives at a mine, the miners compare this new food type with the previous two (or fewer if fewer than two deliveries have occurred at that mine), and:

• If these deliveries are all the same food type, the miners produce $1$ unit of coal.
• If there are exactly two different food types among these deliveries, the miners produce $2$ units of coal.
• If there are three different food types among these deliveries, the miners produce $3$ units of coal.

The types of food trucks and their delivery order are known in advance. By deciding which truck goes to which mine, you can influence the coal output. A food truck cannot be split; each truck must be sent entirely to one mine or the other. The two mines do not need to receive the same number of trucks (indeed, it is allowed to send all trucks to a single mine).

Given the types of food trucks and their delivery order, write a program to decide which truck should be sent to mine $1$ and which to mine $2$ so that the total coal output of the two mines is maximized.

Input Format

The first line contains an integer $N$ $(1 \le N \le 100000)$, the number of food trucks.

The second line contains a string of $N$ characters, in delivery order, representing the type of food carried by each truck. Each character is one of the following three uppercase letters: M (meat), F (fish), or B (bread).

Output Format

Output a single integer: the maximum total coal output.

6
MBMFFB

12

16
MMBMBBBBMMMMMBMB

29

Hint

In sample $1$, you can deliver the trucks in the following sequence: mine $1$, mine $1$, mine $2$, mine $2$, mine $1$, mine $2$, producing $1, 2, 1, 2, 3$, and $3$ units respectively, for a total of $12$ units.

Other delivery plans can also achieve this maximum total.

Translated by ChatGPT 5