اشترى 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).