FJ comprò $N$ $(1 \le N \le 2000)$ gustose leccornie per mucche che ricevono denaro per molto latte. Ne vende una al giorno, massimizzando ricavo su un periodo.

Sono interessanti:

• Numerate $1..N$, ordinate in fila unica in lunga scatola aperta alle due estremità. Ogni giorno ne può prendere una da qualsiasi estremità.
• Come vini pregiati e formaggi gustosi, migliorano e costano di più con età.
• Non uguali, alcune migliori e di maggior valore intrinseco. La leccornia $i$ vale $v(i)$ ($1 \le v(i) \le 1000$).
• Pagano più per più vecchie: età $a$ costa $v(i)*a$.

Dati valori $v(i)$ in ordine di indice $i$ nella scatola, qual è il ricavo massimo con vendite ottimali?

Prima vendita giorno 1, età $a=1$, ogni giorno dopo aumenta età di 1.

Input

• Riga 1: intero $N$.
• Righe $2..N+1$: riga $i+1$, valore $v(i)$.

Output

• Riga 1: ricavo massimo delle vendite.

Esempi

Input 1

5
1
3
1
5
2

Output 1

43

Nota

Vende valori $1, 3, 1, 5, 2$ per indici $1, 5, 2, 3, 4$, guadagna $1*1 + 2*2 + 3*3 + 4*1 + 5*5 = 43$.

Autore: Marco Gallotta (2005).