Descripcion

OCI-cub, un experto en huertos domésticos, cultiva hortalizas de hierba PSN en su huerto casero. En su jardín hay ~N~ macetas alineadas en dirección este-oeste. Estas macetas están numeradas por ~1, ... N~ desde el extremo oeste.

Hay ~N~ gramíneas PSN. En cada maceta hay plantada una hierba PSN.

En primavera, OCI-cub se dio cuenta de que, en contra de sus expectativas, las gramíneas PSN habían producido hojas de varios colores.

Además, descubrió que las hierbas PSN no habían crecido tanto como esperaba. Buscó en los libros y encontró los siguientes datos:

• Hay tres tipos de hierba PSN, con hojas rojas, verdes o amarillas.
• Si las hierbas PSN con el mismo color de hoja se colocan cerca, se impide su crecimiento.

Por lo tanto, OCI-cub decidió reorganizar las macetas para que no se junten hierbas PSN con el mismo color de hoja.

Las macetas son tan pesadas que JOI-kun sólo puede cambiar dos hierbas PSN en macetas vecinas en una sola operación. En otras palabras, lo que OCI-cub puede hacer en una sola operación es elegir una maceta arbitraria ~i~ (~1 \le i \le N - 1~) y luego intercambiar las hierbas PSN en las macetas ~i~ e ~i + 1~.

Tarea

Escribe un programa que, dado el número de hierbas PSN y los colores de las mismas, calcule el mínimo número de operaciones necesarias para reordenar las hierbas PSN de forma que no se junten hierbas PSN con el mismo color de hoja.

Entrada

Lea los siguientes datos de la entrada estándar.

~N~

~S~

~S~ es una cadena de longitud ~N~. Su i-ésimo (~1 \le i \le N~) carácter es ~R~, ~G~, e ~Y~ si el color de la hoja de la hierba PSN en el macetero ~i~ es rojo, verde y amarillo, respectivamente.

Salida

Escriba una línea que contenga el número mínimo de operaciones requeridas en la salida estándar. Si es imposible reordenar las hierbas PSN para que no se junten hierbas PSN con el mismo color de hoja, escriba ~-1~ en su lugar.

Restricciones

• ~1 \le N \le 400~
• ~S~ es una cadena de longitud ~N~.
• Cada carácter de ~S~ es ~R~, ~G~ o ~Y~.

Subtareas

1. (5 puntos) ~N \le 15~.
2. (55 puntos) ~N \le 60~.
3. (15 puntos) Cada carácter de ~S~ es ~R~ o ~G~.
4. (25 puntos) No hay restricciones adicionales.

Ejemplos de entrada y salida

Ejemplos de Entrada #1

5
RRGYY

Ejemplos de Salida #1

2

La siguiente es una forma de reorganizar las gramíneas PSN para que no haya gramíneas PSN con el mismo color de hoja contiguas:

• Primero, intercambia las gramíneas PSN de las macetas ~3~ y ~4~.
• En segundo lugar, intercambia las gramíneas PSN de las macetas ~2~ y ~3~.

Después de esto, el orden de las hierbas Joy será ~RYRGY~. Dado que es imposible reordenar las hierbas PSN con un máximo de ~1~

la respuesta es ~2~.

Ejemplos de Entrada #2

6
RRRRRG

Ejemplos de Salida #2

-1

En este ejemplo, independientemente de las operaciones, es imposible reorganizar las gramíneas PSN de modo que ninguna gramínea PSN con el mismo color de hoja

Ejemplos de Entrada #3

20
YYGYYYGGGGRGYYGRGRYG

Ejemplos de Salida #3

8