Flute's Lemon Transformation

Flute loves lemons. It has prepared a string of shells numbered from \(1\) to \(n\) arranged on a branch. Shell \(i\) has a size \(s_i\). Flute can perform the following magic repeatedly until all shells are taken:

Each time, Flute takes a contiguous segment of shells from one end of the branch and chooses a shell size \(s_0\). If the chosen segment contains \(t\) shells of size \(s_0\), the magic transforms that segment into \(s_0\cdot t^2\) lemons. Note that the chosen size \(s_0\) may be different in different moves. The final number of lemons is the sum of the lemons produced in each move.

Your task is to help Flute determine the maximum number of lemons that can be obtained by optimally choosing the segments and the shell size in each move.

inputFormat

The first line contains a single integer \(n\) \((1 \le n \le 100000)\), representing the number of shells.

The second line contains \(n\) integers \(s_1, s_2, \ldots, s_n\) \((1 \le s_i \le 10000)\), where \(s_i\) denotes the size of the \(i\)th shell in the string.

outputFormat

Output a single integer representing the maximum number of lemons Flute can generate by applying the magic optimally.

sample

3
2 2 2

18