بصفته محباً للعمارة الحديثة، بنى Farmer John حظيرة جديدة دائرية تماماً. داخلها حلقة من $n$ غرفة مرقمة مع عقارب الساعة $1 \ldots n$ حول المحيط ($3 \leq n \leq 100,000$). لكل غرفة باب لكل من جارتيها وباب إلى الخارج.

لديه $n$ بقرة ويريد أن تستقر بقرة واحدة بالضبط في كل غرفة. لكن الأبقار الحائرة تصطف عند أبواب عشوائية، وربما عدة أبقار عند الباب نفسه. تصطف $c_i$ بقرة بالضبط خارج باب الغرفة $i$، لذا $\sum c_i = n$.

تدخل كل بقرة من الباب الذي اصطفت عنده ثم تمشي مع عقارب الساعة عبر الغرف حتى تصل إلى وجهة مناسبة. المرور عبر $d$ باباً يستهلك $d^2$ طاقة. أوجد أقل طاقة كلية لتوزيع الأبقار بحيث تستقر واحدة في كل غرفة.

الإدخال

يحتوي السطر الأول على $n$. تحتوي الأسطر الـ $n$ التالية على $c_1 \ldots c_n$ بالترتيب، قيمة في كل سطر.

الإخراج

اطبع أقل طاقة كلية تستهلكها الأبقار.

أمثلة

الإدخال 1

10
1
0
0
2
0
0
1
2
2
2

الإخراج 1

33

مؤلف المسألة: Brian Dean