Miners

There are two coal mines, each with its own group of miners. Mining coal is hard work, so the miners need food to keep going. Each time a food shipment arrives at a mine, its miners produce some coal. There are three kinds of shipments: meat, fish, and bread.

Miners work harder when their diet is varied. Whenever a new shipment arrives at a mine, its miners consider that shipment together with the two shipments that arrived just before it at the same mine (or fewer, if the mine has received fewer than two shipments so far), and then:

• If all of those shipments are the same kind, they produce 1 unit of coal.
• If they include exactly two different kinds, they produce 2 units of coal.
• If they include all three kinds, they produce 3 units of coal.

You are told in advance the kinds of all shipments and the exact order in which they will be sent. You control the total amount of coal produced by deciding which mine each shipment goes to. A shipment cannot be split: it must go entirely to one mine or the other.

The two mines need not receive the same number of shipments; you may even send every shipment to a single mine.

Given the kinds of the shipments in order, determine the largest total amount of coal that both mines can produce together.

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

The second line contains a string of $N$ characters describing the shipments in the order they will be sent. Each character is one of the uppercase letters M (meat), F (fish), or B (bread).

Print a single integer: the largest total amount of coal that can be produced.

For the shipment string MBMFFB, sending the shipments to mine 1, mine 1, mine 2, mine 2, mine 1, mine 2 respectively yields 1, 2, 1, 2, 3, and 3 units of coal, for a total of 12. Other distributions also reach this maximum.