Treats for the Cows

FJ has purchased $N$ yummy treats ($1 \le N \le 2000$) for the cows who give vast amounts of milk. FJ sells one treat per day and wants to maximize the money he receives over a given period of time.

The treats are interesting for many reasons:

• The treats are numbered 1 to $N$ and stored sequentially in single file in a long box that is open at both ends. On any day, FJ can retrieve one treat from either end of his stash.
• Like fine wines and delicious cheeses, the treats improve with age and command greater prices.
• The treats are not uniform: some are better and have higher intrinsic value. Treat $i$ has value $v(i)$ ($1 \le v(i) \le 1000$).
• Cows pay more for treats that have aged longer: a cow will pay $v(i) \times a$ for a treat of age $a$.

The first treat is sold on day 1 and has age $a=1$. Each subsequent day increases the age by 1.

Given the values $v(i)$ of the treats in order of index $i$ in the box, what is the greatest value FJ can receive for them if he orders their sale optimally?

The first line contains a single integer $N$. Starting from line 2 through line $N+1$, line $i+1$ contains the value $v(i)$ of treat $i$.

Print one line containing the maximum revenue FJ can achieve by selling the treats.