FJ kauft $N$ $(1 \le N \le 2000)$ leckere Leckerbissen für Kühe, die für viel Milch Geld bekommen. Täglich verkauft er einen und maximiert Einnahmen über einen Zeitraum.

Sie sind interessant:

• $1..N$ nummeriert, der Reihe nach einreihig in langem, beidseitig offenem Kasten. Täglich einen von beliebigem Ende entnehmen.
• Wie guter Wein und leckerer Käse werden sie mit Alter besser und teurer.
• Unterschiedlich, manche besser und mit höherem Eigenwert. Stück $i$ hat Wert $v(i)$ ($1 \le v(i) \le 1000$).
• Kühe zahlen für ältere mehr: Alter $a$ bringt $v(i)*a$.

Gegeben Werte $v(i)$ in Indexreihenfolge $i$ im Kasten, was ist der größte Erlös bei optimaler Verkaufsfolge?

Erster Verkauf Tag 1, Alter $a=1$, danach täglich Alter plus 1.

Eingabe

• Zeile 1: Ganzzahl $N$.
• Zeilen $2..N+1$: Zeile $i+1$ enthält Wert $v(i)$.

Ausgabe

• Zeile 1: maximaler Verkaufserlös.

Beispiele

Eingabe 1

5
1
3
1
5
2

Ausgabe 1

43

Hinweis

Werte $1, 3, 1, 5, 2$ verkauft er nach Indizes $1, 5, 2, 3, 4$, Erlös $1*1 + 2*2 + 3*3 + 4*1 + 5*5 = 43$.

Autor: Marco Gallotta (2005).