Chute

Barrels in three colours, red, green and blue, lie in random order on a chute at a port wharf. They have to be rearranged so that the red barrels are at the bottom, the blue ones sit above them, and the green ones are at the top.

A crane does the rearranging. In one move the crane lifts three adjacent barrels off the chute. The barrels that were above them roll down and close the gap, and then the crane puts the three lifted barrels back on the upper end of the chute, keeping their order.

An arrangement of $\ell$ barrels is written as a sequence of $\ell$ letters c, n and z. The letters come from Polish: c is a red barrel (czerwona), n is a blue one (niebieska) and z is a green one (zielona).

One move is named by the position $i$ of the lowest of the three barrels it lifts, counting from the bottom, so $1 \le i \le \ell - 2$. Take nine barrels arranged as (c, z, n, n, c, n, z, z, n). The move $i = 6$ lifts (n, z, z), the single barrel above them rolls down, and the three lifted barrels go back on top, which gives (c, z, n, n, c, n, n, z, z).

At least three of the barrels are green. Under that condition the barrels can always be brought into the red, blue, green order. Find the smallest number of moves that does it.

The first line contains one integer $\ell$ ($3 \le \ell \le 12$), the number of barrels on the chute.

Each of the next $\ell$ lines contains one letter, c, n or z, giving the colour of the next barrel from the bottom of the chute. At least three of these letters are z.

Print one integer, the smallest number of crane moves needed to bring the barrels into the order red at the bottom, then blue, then green. If they already lie in that order, print 0.