#P2149. 电池

电池

本题需要文件读写

文件 IO 为:输入文件 battery.in,输出文件 battery.out。请使用上述文件名读入和输出。

问题描述

有 NN 块电池,电力分别为 A1,A2,…,ANA_1,A_2,\ldots,A_N。选择两块下标不同的电池,设其电力依次为 a,ba,b,产生的总功率为 a×b+a−ba\times b+a-b。

选择顺序不同视为不同取法。请计算最大可能的总功率。

输入格式

从文件 battery.in 中读入数据。

第一行输入一个整数 NN。

第二行输入 NN 个整数 A1,A2,…,ANA_1,A_2,\ldots,A_N。

输出格式

输出到文件 battery.out 中。

输出一行一个整数,表示最大总功率。

样例输入 1

3
5 3 2

样例输出 1

17

样例输入 2

6
1 4 -7 2 8 -5

样例输出 2

37

评测数据规模

所有数据:2≤N≤1052\le N\le10^5,−105≤Ai≤105-10^5\le A_i\le10^5。

测试点 NN 上限 电力范围 特殊性质
1~2 10 −10≤Ai≤10-10\le A_i\le10 所有电力相同
3~4 100 1≤Ai≤1051\le A_i\le10^5 无
5~7 1000 −105≤Ai≤105-10^5\le A_i\le10^5 数组有序
8~10 10510^5 无