FJ kupił $N$ $(1 \le N \le 2000)$ pysznych smakołyków dla krów zarabiających za produkcję dużych ilości mleka. Sprzedaje jeden dziennie, maksymalizuje przychód w okresie.

Są interesujące:

• Numerowane $1..N$, po kolei w jednym szeregu w długim pudełku otwartym z obu końców. Codziennie może wziąć jeden z dowolnego końca.
• Jak dobre wina i pyszne sery, z wiekiem lepsze i droższe.
• Różne, niektóre lepsze i cenniejsze. Smakołyk $i$ ma wartość $v(i)$ ($1 \le v(i) \le 1000$).
• Krowy płacą więcej za starsze: wiek $a$ kosztuje $v(i)*a$.

Dane wartości $v(i)$ według indeksu $i$ w pudełku, jaki maksymalny przychód przy optymalnej kolejności?

Pierwszy sprzedany w dniu 1, wiek $a=1$, potem codziennie wiek rośnie o 1.

Wejście

• Wiersz 1: całkowite $N$.
• Wiersze $2..N+1$: wiersz $i+1$ ma wartość $v(i)$.

Wyjście

• Wiersz 1: maksymalny przychód ze sprzedaży.

Przykład

Wejście 1

5
1
3
1
5
2

Wyjście 1

43

Uwagi

Sprzedaje wartości $1, 3, 1, 5, 2$ według indeksów $1, 5, 2, 3, 4$, zarabiając $1*1 + 2*2 + 3*3 + 4*1 + 5*5 = 43$.

Autor: Marco Gallotta (2005).