A. Attendance Anxiety
time limit per test
0.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

At UFBA, Marina is trying to decide on which days she should attend a demanding review session before the next GruPro selection contest.

For each of the next $$$N$$$ days, attending on day $$$i$$$ gives her a benefit of $$$a_i$$$, which may even be negative if she is already too exhausted.

If Marina attends on several consecutive days, that forms a single streak. A streak of length $$$L$$$ causes a fatigue penalty of $$$L^2$$$. In other words, if the attended days are partitioned into maximal consecutive streaks of lengths $$$L_1, L_2, \ldots, L_k$$$, then her final score is $$$$$$\left(\sum \text{benefit of all attended days}\right) - \left(L_1^2 + L_2^2 + \cdots + L_k^2\right). $$$$$$

She may skip any days she wants. After all, everyone needs a break sometimes; nobody is made of steel.

Determine the maximum possible final score.

Input

The first line contains an integer $$$N$$$ ($$$1 \le N \le 5000$$$), the number of days.

The second line contains $$$N$$$ integers $$$a_1, a_2, \ldots, a_N$$$ ($$$-10^{9} \le a_i \le 10^{9}$$$), where $$$a_i$$$ is the benefit of attending on day $$$i$$$.

Output

Print a single integer: the maximum possible final score.

Examples
Input
5
4 4 -10 4 4
Output
8
Input
6
1 2 3 4 5 6
Output
9
Note

Explanation for example 1

In the first sample, the best strategy is to attend on days $$$1, 2, 4,$$$ and $$$5$$$. This creates two streaks, each of length $$$2$$$, so the score is $$$$$$ 4 + 4 + 4 + 4 - 2^2 - 2^2 = 8. $$$$$$