FJ comprou $N$ $(1 \le N \le 2000)$ guloseimas deliciosas para vacas que recebem dinheiro por muito leite. Vende uma por dia e maximiza receita num período.

São interessantes:

• Numeradas $1..N$, em sequência numa fila em caixa longa aberta nas duas pontas. Cada dia pode pegar uma de qualquer ponta.
• Como bons vinhos e queijos deliciosos, melhoram e custam mais com idade.
• Diferentes, algumas melhores e de maior valor intrínseco. A guloseima $i$ vale $v(i)$ ($1 \le v(i) \le 1000$).
• Vacas pagam mais por antigas: idade $a$ custa $v(i)*a$.

Dados valores $v(i)$ em ordem de índice $i$ na caixa, qual receita máxima com vendas ótimas?

Primeira venda dia 1, idade $a=1$, cada dia depois aumenta idade em 1.

Entrada

• Linha 1: inteiro $N$.
• Linhas $2..N+1$: linha $i+1$, valor $v(i)$.

Saída

• Linha 1: receita máxima das vendas.

Exemplos

Entrada 1

5
1
3
1
5
2

Saída 1

43

Nota

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

Autor: Marco Gallotta (2005).