6951: 小烈上菜

小烈一下碰碰车就被乐满地的工作人员抓住了。作为扰乱秩序的惩罚，小烈必须去乐满地里的“漓江村”饭店端盘子。服务员的工作很繁忙。他们要上菜，同时要使顾客们尽量高兴。一位服务生为n 个顾客上菜。这n 个顾客坐成一排，小烈从一端的厨房中端出n 盘菜(不要问我为什么小烈能一下子端住2500 盘菜，他就是能。)，为n 个顾客各上一道相同的菜。显然，小烈需要走一个来回，如图：

      本来，小烈可以按1，2，3……n 的顺序一次给每个顾客上菜，但是，聪明的小烈通过观察发现，每个顾客都有一个开心值H1，H2，H3……，Hn ，离厨房最近的为H1，然后依次为H2，H3……，Hn。若小烈给第j 位顾客上菜前刚刚为第i 位顾客上菜，则第j 位就会高兴，产生高兴指数Wj=Hi×Hj 。这样，如果小烈按一定的方式调整上菜顺序，可以得到更高的高兴指数。现在小烈想知道用某一方法可达到的n 位顾客高兴指数之和的最大值S。因为顾客越高兴，给小烈的小费越多。第一位上菜的顾客不产生高兴值

第一行一个数，n，顾客的数目
第二行n 个数，第i 个数表示第i 位顾客的开心值。各个数字用空格隔开。

一个数s，为高兴指数的最大值

【样例说明】
从左往右上1 的菜，再上9 的菜，高兴值是0*1+1*9，从右往左走回来的时候上7 的菜，高
兴值是7*9，总的高兴值就是72。
【数据规模】
对于30%的数据n≤9，n∈N+
对于70%的数据n≤1500，n∈N+
对于100%的数据n≤2500，n∈N+
所有数字小于（含结果）
2147483648