You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

$\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$ 只柠檬。再从右端取下最后一只贝壳，通过魔法可以得到 $1×3^1 = 3$ 只柠檬。总共可以得到 $18+3=21$ 只柠檬。没有比这更优的方案了。