Happy Cow

Minho keeps one cow that he cares about. The cow's happiness is his own happiness, so he spent everything he had on $N$ portions of the tastiest feed.

To keep the feed tidy Minho put the portions in order into a warehouse that is narrow but very long, and he calls them feed 1, feed 2, feed 3, ..., feed $N$ counting from the left. Each portion can make the cow feel a different amount of happiness. Eating feed 1 may give the cow 20 happiness while feed 2 gives 10. Call that number the happiness value of the portion.

Feed ripens as days pass and tastes better. If the cow eats a portion with happiness value $H$ on day $d$, the cow feels $H \times d$ happiness. The day of the purchase is day 1 and the next day is day 2.

Feed aged for a million years would be bliss for the cow, but Minho cannot wait that long. He decided to give the cow one portion a day, from the day he bought the feed through day $N$. The warehouse is too narrow to pull a portion out of the middle, so he can only take one from the left end or from the right end. That is, if portions $i$ through $j$ ($1 \le i \le j \le N$) are left, Minho must pick feed $i$ or feed $j$. He cannot give any portion other than $i$ or $j$.

Minho wants the cow to be as happy as possible. Find the maximum total happiness the cow feels when all portions are given over $N$ days.

The first line contains the number of portions $N$ ($1 \le N \le 2000$).

The second line contains the $N$ happiness values $H_1, H_2, \dots, H_N$ ($1 \le H_i \le 1000$), separated by spaces.

Print the maximum total happiness the cow feels when all portions are given over $N$ days.