활강로

항구 부두의 활강로에 빨간색, 초록색, 파란색 통이 아무 순서로나 놓여 있다. 이 통을 빨간색이 맨 아래, 그 위에 파란색, 초록색이 맨 위에 오도록 다시 정리해야 한다.

정리는 크레인이 한다. 크레인은 한 번의 이동에서 활강로 위에 나란히 붙어 있는 통 세 개를 집어 올린다. 그 위에 있던 통은 굴러 내려와 빈자리를 메우고, 크레인은 집어 올린 통 세 개를 순서 그대로 활강로 맨 위에 다시 놓는다.

통 $\ell$개의 배치는 c, n, z 세 글자로 이루어진 길이 $\ell$의 수열로 적는다. 글자는 폴란드어에서 왔다. c는 빨간색(czerwona), n은 파란색(niebieska), z는 초록색(zielona) 통이다.

이동 하나는 집어 올리는 통 세 개 가운데 가장 아래에 있는 통의 위치 $i$로 나타내며, 아래에서부터 세어 $1 \le i \le \ell - 2$이다. 예를 들어 통 아홉 개가 (c, z, n, n, c, n, z, z, n)으로 놓여 있을 때 $i = 6$인 이동은 (n, z, z)를 집어 올린다. 그 위의 통 하나가 굴러 내려오고 집어 올린 세 개가 맨 위에 다시 놓이므로 배치는 (c, z, n, n, c, n, n, z, z)가 된다.

초록색 통은 적어도 세 개 있다. 그러면 통을 언제나 빨강, 파랑, 초록 순서로 정리할 수 있다. 필요한 이동 횟수의 최솟값을 구하시오.

첫째 줄에 활강로 위의 통 개수 $\ell$이 주어진다. ($3 \le \ell \le 12$)

다음 $\ell$개 줄에는 각각 글자 c, n, z 중 하나가 주어진다. 활강로 아래쪽부터 차례로 통의 색을 나타낸다. 이 가운데 z는 적어도 세 개다.

통을 아래에서부터 빨강, 파랑, 초록 순서로 만드는 데 필요한 크레인 이동 횟수의 최솟값을 한 줄에 출력한다. 이미 그 순서로 놓여 있으면 0을 출력한다.