Description

$\text{Flute}$ likes lemons very much. It prepared a string of shells threaded onto a branch and plans to use a kind of magic to turn the shells into lemons. There are $n$ $(1 \le n \le 100000)$ shells in total, threaded on the branch in order. For convenience, we number the shells from left to right as $1..n$. The sizes of the shells are not necessarily the same; the size of shell $i$ is $s_i(1 \le s_i \le 10000)$.

The lemon-making magic requires that: each time, $\text{Flute}$ removes a short consecutive segment of shells from one end of the branch, and chooses a shell size $s_0$. If there are $t$ shells of size $s_0$ in this segment, then the magic can turn this segment into $s_0 t^2$ lemons. $\text{Flute}$ may remove shells any number of times until all shells on the branch have been removed. For different segments, the chosen shell size $s_0$ may be different. The final number of lemons $\text{Flute}$ gets is the sum of the lemons obtained from all segments.

$\text{Flute}$ wants to know the maximum number of lemons that can be produced from this string of shells. Please help solve this problem.

Input Format

Line $1$: an integer $n$.

Lines $2..n+1$: each line contains one integer; line $i+1$ gives $s_i$.

Output Format

A single integer, meaning the maximum number of lemons $\text{Flute}$ can obtain.

5
2
2
5
2
3

21

Hint

$\text{Flute}$ first removes $4$ shells from the left end, with sizes $2, 2, 5, 2$. Choose $s_0 = 2$. Then there are $3$ shells of size $s_0$ in this segment, so the magic yields $2 \times 3^2 = 18$ lemons. Then remove the last shell from the right end, and the magic yields $3 \times 1^2 = 3$ lemons. In total, you can get $18 + 3 = 21$ lemons. There is no better plan than this.

Translated by ChatGPT 5