4137. [JSOI2011] 柠檬

【题目描述】

$\text{Flute}$ 很喜欢柠檬。它准备了一串用树枝串起来的贝壳，打算用一种魔法把贝壳变成柠檬。贝壳一共有 $n$ $(1≤n≤100000)$ 只，按顺序串在树枝上。为了方便，我们从左到右给贝壳编号 $1..n$ 。每只贝壳的大小不一定相同，贝壳 $i$ 的大小为 $s_i(1≤s_i≤10000)$ 。

变柠檬的魔法要求$:\ \text{Flute}$ 每次从树枝一端取下一小段连续的贝壳，并选择一种贝壳的大小 $s_0$。如果这一小段贝壳中大小为 $s_0$ 的贝壳有 $t$ 只，那么魔法可以把这一小段贝壳变成 $s_0t^2$ 只柠檬。$\text{Flute}$ 可以取任意多次贝壳，直到树枝上的贝壳被全部取完。各个小段中，$\text{Flute}$ 选择的贝壳大小 $s_0$ 可以不同。而最终 $\text{Flute}$ 得到的柠檬数，就是所有小段柠檬数的总和。

$\text{Flute}$ 想知道，它最多能用这一串贝壳

变出多少柠檬。请你帮忙解决这个问题。

【输入格式】

第 $1$ 行：一个整数，表示 $n$ 。

第 $2..n+1$ 行：每行一个整数，第 $i+1$ 行表示 $s_i$。

【输出格式】

仅一个整数，表示 $\text{Flute}$ 最多能得到的柠檬数。

【样例输入】

5
2
2
5
2
3

【样例输出】

21

【数据范围】

$\text{Flute}$ 先从左端取下 $4$ 只贝壳，它们的大小为 $2, 2, 5, 2$。选择 $s_0=2$，那么这一段里有 $3$ 只大小为 $s_0$ 的贝壳，通过魔法可以得到 $2×3^2 = 18$ 只柠檬。再从右端取下最后一只贝壳，通过魔法可以得到 $3×1^2 = 3$ 只柠檬。总共可以得到 $18+3=21$ 只柠檬。没有比这更优的方案了。