FJ купил $N$ $(1 \le N \le 2000)$ вкусных лакомств коровам, получающим деньги за много молока. Продаёт одно в день, максимизируя доход за период.

Лакомства интересны:

• Номера $1..N$, по порядку в один ряд в длинной коробке, открытой с двух концов. Ежедневно можно взять одно с любого конца.
• Как хорошее вино и сыр, с возрастом лучше и дороже.
• Неодинаковые, некоторые лучше и ценнее. Лакомство $i$ имеет стоимость $v(i)$ ($1 \le v(i) \le 1000$).
• За старое платят больше: за возраст $a$ корова платит $v(i)*a$.

Даны стоимости $v(i)$ в порядке индекса $i$ в коробке; каков максимальный доход при оптимальном порядке продаж?

Первое продано в день 1 с возрастом $a=1$, каждый следующий день добавляет 1 к возрасту.

Входные данные

• Строка 1: целое $N$.
• Строки $2..N+1$: строка $i+1$ содержит стоимость $v(i)$.

Выходные данные

• Строка 1: максимальный доход от продаж.

Примеры

Входные данные 1

5
1
3
1
5
2

Выходные данные 1

43

Примечание

FJ продаёт стоимости $1, 3, 1, 5, 2$ в порядке индексов $1, 5, 2, 3, 4$, получая $1*1 + 2*2 + 3*3 + 4*1 + 5*5 = 43$.

Автор: Marco Gallotta (2005).