水平辺、垂直辺、および $N$ 個の頂点からなる多角形 $P$ を考えます。その辺は端点でのみ交わることができ、各頂点ではちょうど 2 本の辺の端点が接します。$P$ の辺に沿って反時計回りに進むと、各頂点で左または右に曲がります。左折を $L$、右折を $R$ と表すと、$L$ と $R$ からなる文字列で多角形を表せます。例えば、図 1 の多角形は次の文字列で表されます。

$LLRLLRRLLRLLRLLRRLLR$

文字列で多角形を表すときは、常に多角形の最も左の辺の上側の端点から始めます。この文字は常に $L$ です。

図 1 と図 2

与えられた文字列で表される多角形は、次の条件を満たす必要があります。任意の垂直な直線 $V$ について、$V$ と多角形の水平辺の内部（端点を除く部分）との交点は高々 2 個です。

多角形 $P$ に対し、$P$ を含む、辺が水平または垂直な最小の長方形を $B(P)$ とします。これは $P$ の最も左、右、上、下の辺に重なる垂直または水平な直線によって決まります（図 2）。

$L$ と $R$ からなる長さ $N$ の文字列が与えられたとき、それが表す多角形 $P$ で上の条件を満たすものを描きます。$P$ の各辺の長さは整数でなければなりません。$B(P)$ の面積を最小にし、その最小値を出力するプログラムを作成してください。

採点プログラムのために次の関数を実装してください。

int polygon(string S);

この関数は、各文字が $L$ または $R$ である長さ $N$ の文字列 $S$ を受け取ります。$S$ が表す多角形 $P$ のうち、$B(P)$ の面積を最小にするものを求め、その面積を返してください。

実装の詳細

polygon.c または polygon.cpp という名前のファイルをちょうど 1 つ提出し、次の関数を実装してください。

int polygon(string S);

この関数は上記の通り動作する必要があります。内部で使うほかの関数を作成しても構いません。提出コードは入出力やほかのファイルへのアクセスを行ってはいけません。

採点プログラムの例

配布される採点プログラムは、次の形式で入力を読みます。

• 1 行目：$N$（文字列の長さ）。

• 2 行目：長さ $N$ の文字列 $c_1c_2\cdots c_N$（$c_1=L$、$2\le i\le N$ について $c_i=L$ または $R$）。

配布される採点プログラムは polygon の戻り値を出力します。

制約

• 入力文字列は $L$ と $R$ からなります。

• 入力文字列で表され、上記の条件を満たす多角形が少なくとも 1 つ必ず存在します。

• $4 \le N \le 800$.

小課題

1 (20 点)

• $N \le 10$.

2 (36 点)

• $N \le 40$.

3 (21 点)

• $N \le 100$.

4 (73 点)

• 追加の制約はありません。

入出力例

入力 1

8
LLLRRLLL

出力 1

6

入力 2

20
LLRLLRRLLRLLRLLRRLLR

出力 2

15