#NC21841. 牛牛玩平板

牛牛玩平板

题目描述

牛牛和牛妹喜欢玩平板游戏,游戏一开始屏幕上会出现很多个图形,玩家在每一轮可以合并两个图形,当只有一个图形的时候游戏结束,每个图形都有一个大小,合并完成后的图形的大小为x+y,x和y分别为合并之前的两个图形,与此同时,玩家会获得x*y的分数。 牛牛和牛妹新开了一盘游戏,屏幕上出现了n个图形,每个图形的大小已知,请算出牛牛和牛妹最大能获得的分数

输入格式

第一行输入一个整数 nn,表示图形的数量。

第二行输入 nn 个整数,分别表示图形的大小,每个整数的范围为 11 到 100100。

输出格式

输出一个整数

提示

子任务1:n <= 10 子任务2:n <= 20 子任务3:无限制

样例 1

3
1 2 3
11

样例 2

2
3 4
12

样例 3

3
2 2 2
12

来源

牛客原题