FJ קנה $N$ $(1 \le N \le 2000)$ חטיפים טעימים לפרות המקבלות כסף על חלב רב. מוכר אחד ביום וממקסם הכנסה בתקופה.

הם מעניינים:

• ממוספרים $1..N$, לפי הסדר בשורה אחת בקופסה ארוכה פתוחה בשני הקצוות. כל יום אפשר לקחת אחד מכל קצה לבחירה.
• כמו יין משובח וגבינה טעימה, משתפרים ומתייקרים עם הגיל.
• שונים, חלק טובים וערכם הפנימי גבוה. חטיף $i$ בערך $v(i)$ ($1 \le v(i) \le 1000$).
• פרות משלמות יותר לישנים: בגיל $a$ משלמות $v(i)*a$.

נתונים ערכי $v(i)$ בסדר אינדקס $i$ בקופסה, מה ההכנסה המרבית בסדר מכירה מיטבי?

הראשון נמכר ביום 1, גיל $a=1$, כל יום הבא מגדיל גיל ב־1.

קלט

• שורה 1: שלם יחיד $N$.
• שורות $2..N+1$: שורה $i+1$ ערך $v(i)$.

פלט

• שורה 1: הכנסה מרבית ממכירה.

דוגמאות

קלט 1

5
1
3
1
5
2

פלט 1

43

הערה

ערכים $1, 3, 1, 5, 2$ נמכרים באינדקסים $1, 5, 2, 3, 4$, רווח $1*1 + 2*2 + 3*3 + 4*1 + 5*5 = 43$.

מחבר: Marco Gallotta (2005).