Article From:https://www.cnblogs.com/dream-maker-yk/p/9732656.html

### Description

Flute I like lemon very much. It prepares a bunch of shells that are strung together with branches, and intends to use a magic trick to turn shells into lemons. Shells have N (1 or less than N or less than 100000) only, and they are arranged on the branches in sequence. For convenience, we shell 1..N from left to right. Each shellThe size of shells is not the same. The size of shell I is Si (1 Si or less than 10000). The magic of changing lemons requires Flute to take a small piece of continuous shells from one end of the branch at a time and select a shell size s0. If the shell is small in sizeThe shell of S0 has t, so magic can turn this little shell into s0t^2 lemon. Flute can take shells for many times until the shells on the branches are all taken away. In each segment, the shell size S0 selected by Flute can be different. In the endThe number of lemons obtained by Flute is the sum of all small segments of lemon. Flute wants to know how much lemon it can produce with the shellfish. Please help solve this problem.

### Input

The first line: an integer indicating N.
Second. N + 1 rows: one integer for each row, and I + 1 row for Si.

### Output

There is only one integer representing the maximum number of lemons that Flute can get.

5
2
2
5
2
3

### Sample Output

21
//Flute First take 4 shells from the left side, their size is 2, 2, 5, 2. Choose S0 = 2, and there are three shells the size of S0 in this section. By magic, you can get 2 x 3 ^ 2 = 18 lemons. Then take the last shell from the right side.By magic, you can get 1 x 3^1 = 3 lemons. A total of 18 + 3 = 21 lemon. There is no better plan than this.