FJ achète $N$ $(1 \le N \le 2000)$ friandises pour les vaches qui gagnent de l'argent grâce à beaucoup de lait. Il en vend une par jour et maximise son revenu sur une période.

Elles sont intéressantes :

• Numérotées $1..N$, rangées en une file dans une longue boîte ouverte aux deux bouts. Chaque jour FJ peut en prendre une à l'un ou l'autre bout.
• Comme bons vins et délicieux fromages, meilleures et plus chères avec l'âge.
• Différentes, certaines meilleures, valeur intrinsèque supérieure. Friandise $i$ de valeur $v(i)$ ($1 \le v(i) \le 1000$).
• Les vaches paient davantage pour des friandises plus âgées : pour âge $a$, prix $v(i)*a$.

Les valeurs $v(i)$ rangées par indice $i$ sont données ; quel revenu maximal avec ordre de vente optimal ?

Première vente au jour 1, âge $a=1$, puis chaque jour l'âge augmente de 1.

Entrée

• Ligne 1 : un entier $N$.
• Lignes $2..N+1$ : ligne $i+1$, valeur $v(i)$.

Sortie

• Ligne 1 : revenu maximal de vente.

Exemples

Entrée 1

5
1
3
1
5
2

Sortie 1

43

Remarque

FJ vend les valeurs $1, 3, 1, 5, 2$ dans l'ordre des indices $1, 5, 2, 3, 4$, gagnant $1*1 + 2*2 + 3*3 + 4*1 + 5*5 = 43$.

Auteur : Marco Gallotta (2005).