Considere um polígono $P$ com lados horizontais e verticais e $N$ vértices. Seus lados só podem se encontrar nas extremidades, e em cada vértice encontram-se exatamente duas extremidades de lados. Ao percorrer os lados de $P$ no sentido anti-horário, viramos à esquerda ou à direita em cada vértice. Representamos uma virada à esquerda por $L$ e à direita por $R$. Assim, uma string de $L$ e $R$ representa o polígono. Por exemplo, o polígono da figura 1 é representado por

$LLRLLRRLLRLLRLLRRLLR$

Ao representar um polígono por uma string, sempre começamos na extremidade superior do lado mais à esquerda. Esse caractere é sempre $L$.

Figuras 1 e 2

Um polígono representado pela string dada deve satisfazer a seguinte condição: para qualquer reta vertical $V$, há no máximo duas interseções de $V$ com os interiores dos lados horizontais do polígono (excluindo suas extremidades).

Para um polígono $P$, seja $B(P)$ o menor retângulo com lados horizontais e verticais que contém $P$. Ele é determinado pelas retas verticais e horizontais que coincidem com os lados mais à esquerda, à direita, acima e abaixo de $P$ (figura 2).

Dada uma string de comprimento $N$ composta por $L$ e $R$, desenhamos um polígono $P$ representado por ela que satisfaz a condição acima. O comprimento de cada lado de $P$ deve ser inteiro. Escreva um programa que minimize a área de $B(P)$ e imprima esse mínimo.

Você deve implementar a seguinte função para o avaliador.

int polygon(string S);

A função recebe uma string $S$ de comprimento $N$, cujos caracteres são $L$ ou $R$. Entre os polígonos $P$ representados por $S$, encontre um que minimize a área de $B(P)$ e retorne essa área.

Detalhes de implementação

Envie exatamente um arquivo chamado polygon.c ou polygon.cpp. Ele deve implementar a seguinte função.

int polygon(string S);

A função deve funcionar conforme descrito acima. Você pode criar outras funções para uso interno. O código enviado não deve realizar entrada/saída nem acessar outros arquivos.

Avaliador de exemplo

O avaliador fornecido lê a entrada no seguinte formato.

• Linha 1: $N$ (o comprimento da string).

• Linha 2: uma string $c_1c_2\cdots c_N$ de comprimento $N$ ($c_1=L$, e $c_i=L$ ou $R$ para $2\le i\le N$).

O avaliador fornecido imprime o valor retornado por polygon.

Restrições

• A string de entrada é composta por $L$ e $R$.

• Sempre existe pelo menos um polígono representado pela string de entrada que satisfaz as condições acima.

• $4 \le N \le 800$.

Subtarefas

1 (20 pontos)

• $N \le 10$.

2 (36 pontos)

• $N \le 40$.

3 (21 pontos)

• $N \le 100$.

4 (73 pontos)

• Sem restrições adicionais.

Exemplos

Entrada 1

8
LLLRRLLL

Saída 1

6

Entrada 2

20
LLRLLRRLLRLLRLLRRLLR

Saída 2

15