考慮一個由水平邊、垂直邊以及 $N$ 個頂點組成的多邊形 $P$。多邊形的邊只能在端點處相交，每個頂點處恰有兩條邊的端點相接。沿著 $P$ 的邊逆時針移動時，在每個頂點處會向左或向右轉。用 $L$ 表示左轉，用 $R$ 表示右轉，就可以用一個由 $L$ 和 $R$ 組成的字串表示多邊形。例如，圖 1 中的多邊形可以表示為

$LLRLLRRLLRLLRLLRRLLR$

用字串表示多邊形時，始終從多邊形最左側邊的上端點開始。這個字元總是 $L$。

圖 1 和圖 2

給定字串表示的多邊形必須滿足以下條件：對於任意垂直直線 $V$，$V$ 與多邊形各水平邊的內部（不包括端點）至多有兩個交點。

對於多邊形 $P$，用 $B(P)$ 表示包含 $P$ 的、各邊水平或垂直的最小矩形。它由分別與 $P$ 最左、最右、最上、最下的邊重合的垂直或水平直線確定（圖 2）。

給定一個由 $L$ 和 $R$ 組成的長度為 $N$ 的字串，繪製一個由該字串表示且滿足上述條件的多邊形 $P$。$P$ 的每條邊長都必須為整數。請編寫程式，使 $B(P)$ 的面積最小，並輸出該最小值。

你需要為評測程式實作下面的函式。

int polygon(string S);

該函式接收一個長度為 $N$ 的字串 $S$，其中每個字元為 $L$ 或 $R$。在 $S$ 表示的多邊形 $P$ 中，找到使 $B(P)$ 面積最小的多邊形，並回傳該面積。

實作細節

你必須恰好提交一個名為 polygon.c 或 polygon.cpp 的檔案，其中實作以下函式。

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$ 組成。

• 輸入字串所表示的、滿足上述條件的多邊形至少存在一個。

• $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