背景

那个男人远了，远了，到了颓圮的篱墙，走尽这机房.......
题目描述
那个男人准备走了，前往幻想乡去享受无穷无尽的快乐......
作为一个幽（wei）默（suo）的男人，他肯定不会就这样悄无声息地离去，于是，他又一次回到了机房，作为机房里的大佬，那个男人给机房里的朋友们留下了一大盒巧克力（话说真的需要不少钱），并把一块块巧克力排成了一排，已知总共有n（n<=5000）块巧克力。
yzq是一个萌新，他毫不客气地吃掉了一块，却嚎叫着吐了出来，原来巧克力是苦的。那个男人微微一笑，告诉机房里的人，巧克力有的是甜的，有的是苦的，而yzq是喜欢吃甜的巧克力，对于每一块巧克力，yzq都对它有一个中意度，对于甜的巧克力，中意度是正数，而对苦的巧克力，中意度是负数。
那个男人又给了yzq一个机会，yzq可以选择任意多块连续的巧克力，其中可能有甜的巧克力，可能有苦的巧克力，对于每一个区间，yzq定义区间中意度为区间内任意两块巧克力的中意度的乘积的和，注意，区间中意度的乘积不能重复计算。
yzq是一个蒟（大）蒻（佬），他不知道怎样才能获得最大的区间中意度，所以，他来向你请教。

输入

输入一个数n，表示有n块巧克力。
接下来n个数，分别表示对于每一块巧克力yzq对它的中意度。
输入

输出一个数，表示最大的区间中意度。
样例 1

输入样例1
10
-1 5 6 9 2 -3 1 7 8 5

输出样例1

653

限制

Time Limit:2000ms Memory Limit:128MB
数据范围
对于20%的数据，保证n<=50。
对于50%的数据，保证n<=300。
对于100%的数据，保证n<=5000。
对于100%的数据，保证-int<=a[i]<=int。