Magic Photo Studio Wait Time

In a magical photo studio, there are three curtains arranged from left to right in the order red, blue, and white.

The photographer adjusts the curtains by either raising or lowering them. Each adjustment takes 1 time unit, while taking a photo costs 0 time units. The background color of a photo is determined by the following rule: when viewing the curtains from right to left, the first curtain that is not raised (i.e. still down) determines the background color.

Specifically, to achieve the desired background color:

• For white: the rightmost (white) curtain must be down.
• For blue: the rightmost (white) curtain must be raised and the middle (blue) curtain must be down.
• For red: both the rightmost (white) and the middle (blue) curtains must be raised, and the leftmost (red) curtain must be down.

Initially, all curtains are down. There are a total of n customers in line ahead of little M, and each customer specifies a desired background color (either red, blue, or white) for their photo. The photographer processes the customers in order by adjusting the curtains. Note that for each customer, if a curtain's state does not affect the resulting background (because it is not the first not raised when scanning from right to left), its final state can be chosen arbitrarily to potentially minimize future adjustments.

Your task is to compute the minimum total time (in units) needed for the photographer to adjust the curtains to meet all the customers' requests.

Hint: You can model each state of the three curtains as a triplet where 0 denotes down and 1 denotes up. If we encode the state as a three‐bit integer (with the left curtain as the most significant bit and the right curtain as the least significant bit), the conditions are:

• For white: the least significant bit is 0.
• For blue: the least significant bit is 1 and the middle bit is 0.
• For red: the bit pattern must be 0 1 1 (in binary, this is \(\mathtt{011}\)).

The cost to transition between states is the Hamming distance between the two 3-bit states. Optimize the sequence of state transitions accordingly.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of customers. Each of the next n lines contains a string (red, blue, or white) which represents a customer’s request.

outputFormat

Output a single integer, the minimum total time units required for all the curtain adjustments.

sample

3
white
blue
red

3