כחובב אדריכלות מודרנית, 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