Harvest

Rice plants are planted in a single row across a long 1 × N field. Junhee wants to harvest all of them. To reach a plant in the middle you would have to push your way through the field, so at each step you may harvest only one of the two plants currently at the ends of the row. At first you may harvest either the 1st plant or the N-th plant; if you harvest the 1st plant, then next you may harvest either the 2nd plant or the N-th plant, and so on.

The profit from a harvest is computed as follows: if a plant has value v and it is the k-th plant you harvest, you earn v × k from it.

For example, if the plant values from left to right are 1, 3, 1, 5, 2 and you harvest the plants at positions 1, 5, 2, 3, 4 in that order, the profit is 1×1 + 2×2 + 3×3 + 1×4 + 5×5 = 43, which is the maximum profit obtainable from this field.

Given the number of plants N and the value of each plant, write a program that finds the maximum total profit obtainable by harvesting all of the plants.

The first line contains the number of plants N (1 ≤ N ≤ 2,000). Each of the next N lines contains the value v (1 ≤ v ≤ 1,000) of a plant, given from left to right, one per line.

Print the maximum obtainable profit on the first line.