U149793 Aurora的刷题计划

 # Aurora AK IOI everyday！

Aurora放寒假了！（**Au** rora，指金牌rora） 它决定利用寒假的时间好好刷题，争取明年不止AKIOI，而是AKZJOI！ 何老板非常支持Aurora的想法。寒假一共有 $n(1\le n\le 2\times 10^6)$ 天，何老板给Aurora每天都安排了一道题，由Aurora自己选择刷不刷这道题，但是Aurora实在是太强了，有些题对于Aurora来说太水了，反而会降低它的水平。 第 $i$ 天的题目难度系数为 $w_i$（$-10^6\le w_i\le 10^6$）。每刷一道难度系数为 $x$ 的题，Aurora的水平就会增加 $x$。由于Aurora过于强大，你可以认为他的初始水平是无限的。但是，在别人都在努力学习的寒假，Aurora只要连续 $k$ 天不刷题，他的水平就会减少 $k^2$。 Aurora和何老板当然都希望**整个寒假都结束**后，Aurora的水平尽量高。现在，Aurora把安排整个寒假的刷题计划这个光荣，伟大，艰难，辉煌的使命交给了你，问你整个寒假结束后Aurora水平最多能提高多少（有可能存在Aurora无论如何整个寒假过后水平都会降低情况，这个时候输出应为负数）。

第一行，一个整数 $n$，表示整个寒假的天数。 第二行，$n$ 个用空格间隔的整数，表示每道题目的 $w_i$。

输出仅一行，一个整数，表示Aurora的水平最大能提高多少。

对于样例一，在第三天刷题，则前两天没刷题，水平降低 $2^2=4$，后两天没刷题，水平降低 $2^2=4$，然后第三天的题目难度为 $-5$，水平总共提高 $-5-4-4=-13$。 样例二，刷 $1,3,5,6,8$ 天的题。 样例三，一道题不刷。 | 测试点编号 | 数据范围 | 特殊性质 | | :---------: | :-----------: | :-----------: | | $1,2$ | $n\le 5000$ | 无 | | $3$ | $n\le 10^6$ | $w_i$ 均为非负数 | | $4$ | $n\le 10^4$ | 无 | | $5,6$ | $n\le 2\times 10^4$ | 无 | | $7,8$ | $n\le 5\times 10^4$ | 无 | | $9,10$ | $n\le 10^5$ | 无 | | $11$ | $n\le 10^5$ | $w_i$ 均为负数 | | $12,13$ | $n\le 2\times 10^5$ | 无 | | $14,15$ | $n\le 5\times 10^5$ | 无 | | $16$ | $n\le 10^6$ | 无 | | $17\sim 20$ | $n\le 2\times 10^6$ | 无 |