لنعتبر مضلعًا $P$ له أضلاع أفقية ورأسية و$N$ رؤوس. لا يمكن أن تتلاقى أضلاعه إلا عند نهاياتها، ويلتقي عند كل رأس طرفا ضلعين بالضبط. عند السير على أضلاع $P$ عكس اتجاه عقارب الساعة، ننعطف يسارًا أو يمينًا عند كل رأس. نرمز للانعطاف يسارًا بـ $L$ وللانعطاف يمينًا بـ $R$. وهكذا تمثل سلسلة من $L$ و$R$ المضلع. على سبيل المثال، يُمثل المضلع في الشكل 1 بالسلسلة

$LLRLLRRLLRLLRLLRRLLR$

عند تمثيل مضلع بسلسلة، نبدأ دائمًا من الطرف العلوي لضلع المضلع الأيسر. يكون هذا المحرف دائمًا $L$.

الشكلان 1 و2

يجب أن يحقق المضلع الممثل بالسلسلة المعطاة الشرط التالي: لكل خط رأسي $V$، يوجد على الأكثر تقاطعان لـ $V$ مع الأجزاء الداخلية للأضلاع الأفقية للمضلع (باستثناء نهاياتها).

للمضلع $P$، نرمز بـ $B(P)$ إلى أصغر مستطيل ذي أضلاع أفقية ورأسية يحتوي $P$. تحدده الخطوط الرأسية والأفقية المنطبقة على أضلاع $P$ الأيسر والأيمن والأعلى والأسفل (الشكل 2).

عند إعطاء سلسلة طولها $N$ وتتكون من $L$ و$R$، نرسم مضلعًا $P$ تمثله هذه السلسلة ويحقق الشرط أعلاه. يجب أن يكون طول كل ضلع من $P$ عددًا صحيحًا. اكتب برنامجًا يصغر مساحة $B(P)$ ويطبع قيمتها الدنيا.

يجب تنفيذ الدالة التالية لبرنامج التقييم.

int polygon(string S);

تستقبل الدالة سلسلة $S$ طولها $N$، كل محرف فيها هو $L$ أو $R$. من بين المضلعات $P$ التي تمثلها $S$، أوجد مضلعًا يصغر مساحة $B(P)$ وأعد تلك المساحة.

تفاصيل التنفيذ

يجب إرسال ملف واحد بالضبط اسمه polygon.c أو polygon.cpp. يجب أن ينفذ الملف الدالة التالية.

int polygon(string S);

يجب أن تعمل الدالة كما وُصف أعلاه. يمكنك إنشاء دوال أخرى للاستخدام الداخلي. يجب ألا ينفذ الكود المرسل عمليات إدخال أو إخراج، وألا يصل إلى ملفات أخرى.

مثال برنامج التقييم

يقرأ برنامج التقييم المرفق الإدخال بالصيغة التالية.

• السطر 1: $N$ (طول السلسلة).

• السطر 2: سلسلة $c_1c_2\cdots c_N$ طولها $N$ ($c_1=L$، و$c_i=L$ أو $R$ عندما $2\le i\le N$).

يطبع برنامج التقييم المرفق القيمة التي تعيدها 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