Considera un polígono $P$ con lados horizontales y verticales y $N$ vértices. Sus lados solo pueden encontrarse en sus extremos, y en cada vértice se encuentran exactamente dos extremos de lados. Al recorrer los lados de $P$ en sentido antihorario, giramos a la izquierda o a la derecha en cada vértice. Representamos un giro a la izquierda con $L$ y uno a la derecha con $R$. Así, una cadena de $L$ y $R$ representa el polígono. Por ejemplo, el polígono de la figura 1 se representa con

$LLRLLRRLLRLLRLLRRLLR$

Al representar un polígono mediante una cadena, se empieza siempre en el extremo superior de su lado más a la izquierda. Este carácter siempre es $L$.

Figuras 1 y 2

Un polígono representado por la cadena dada debe satisfacer la siguiente condición: para cualquier recta vertical $V$, hay como máximo dos intersecciones de $V$ con el interior de los lados horizontales del polígono (excluyendo los extremos).

Para un polígono $P$, sea $B(P)$ el menor rectángulo con lados horizontales y verticales que contiene a $P$. Está determinado por las rectas verticales y horizontales que coinciden con los lados más a la izquierda, a la derecha, arriba y abajo de $P$ (figura 2).

Dada una cadena de longitud $N$ formada por $L$ y $R$, dibujamos un polígono $P$ representado por ella que cumpla la condición anterior. La longitud de cada lado de $P$ debe ser entera. Escribe un programa que minimice el área de $B(P)$ y muestre ese mínimo.

Debes implementar la siguiente función para el evaluador.

int polygon(string S);

La función recibe una cadena $S$ de longitud $N$, cuyos caracteres son $L$ o $R$. Entre los polígonos $P$ representados por $S$, encuentra uno que minimice el área de $B(P)$ y devuelve dicha área.

Detalles de implementación

Debes enviar exactamente un archivo llamado polygon.c o polygon.cpp, que implemente la siguiente función.

int polygon(string S);

La función debe comportarse como se describió antes. Puedes crear otras funciones para uso interno. El código enviado no debe realizar entrada/salida ni acceder a otros archivos.

Evaluador de ejemplo

El evaluador proporcionado lee la entrada en el siguiente formato.

• Línea 1: $N$ (la longitud de la cadena).

• Línea 2: una cadena $c_1c_2\cdots c_N$ de longitud $N$ ($c_1=L$, y $c_i=L$ o $R$ para $2\le i\le N$).

El evaluador proporcionado muestra el valor devuelto por polygon.

Restricciones

• La cadena de entrada está formada por $L$ y $R$.

• Siempre existe al menos un polígono representado por la cadena de entrada que satisface las condiciones anteriores.

• $4 \le N \le 800$.

Subtareas

1 (20 puntos)

• $N \le 10$.

2 (36 puntos)

• $N \le 40$.

3 (21 puntos)

• $N \le 100$.

4 (73 puntos)

• Sin restricciones adicionales.

Ejemplos

Entrada 1

8
LLLRRLLL

Salida 1

6

Entrada 2

20
LLRLLRRLLRLLRLLRRLLR

Salida 2

15