[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}$ 最多能得到的柠檬数。

输入输出样例

输入样例 #1

5
2
2
5
2
3

输出样例 #1

21

说明

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