FJ compró $N$ $(1 \le N \le 2000)$ golosinas deliciosas para vacas que ganan dinero dando mucha leche. Vende una al día y maximiza ingreso durante cierto período.

Son interesantes:

• Numeradas $1..N$, en orden en una sola fila en caja larga abierta por ambos extremos. Cada día puede sacar una de cualquier extremo.
• Como buenos vinos y deliciosos quesos, mejoran y valen más con edad.
• No iguales, algunas mejores y de mayor valor intrínseco. Golosina $i$ vale $v(i)$ ($1 \le v(i) \le 1000$).
• Pagan más por más antiguas: con edad $a$, pagan $v(i)*a$.

Dados valores $v(i)$ por índice $i$ en caja, ¿mayor ingreso con orden óptimo de venta?

Primera venta día 1 con edad $a=1$, cada día posterior suma 1 a edad.

Entrada

• Línea 1: entero $N$.
• Líneas $2..N+1$: línea $i+1$, valor $v(i)$.

Salida

• Línea 1: ingreso máximo de venta.

Ejemplos

Entrada 1

5
1
3
1
5
2

Salida 1

43

Nota

Vende valores $1, 3, 1, 5, 2$ por índices $1, 5, 2, 3, 4$, ganando $1*1 + 2*2 + 3*3 + 4*1 + 5*5 = 43$.

Autor: Marco Gallotta (2005).