题目背景

事实上， 小黑子 们的数量比 ikun 要多得多，但是因为 ikun 们得到了 坤哥 的帮助，他们一直没能打败 ikun ，有一天 坤哥 突然病了， 小黑子 军团的首领 cgy 率领 小黑子 们展开反击。

题目简介

cgy 手下有 \(N\) 名 小黑子 ，第 \(i\) 名 小黑子 的战斗力为 \(Num_i\) 。 cgy 每一次可以将相邻的两个 小黑子 军团合并成一个更大的 小黑子 军团（一个 小黑子 也算作一个军团），此时最终军团的战斗力就会增加两个军团战斗力的和。 cgy 最终会将所有的 小黑子 融合成一个大军团， cgy 意图组织出一个最强的 小黑子 军团，他叫来了你帮忙，希望你可以计算出军团的最大战斗力，

题目数据

第一行一个整数 \(N(N <= 10^3)\) 表示 cgy 手下 小黑子 的数量。
第二行 \(N\) 个整数，第 \(i\) 整数表示第 \(i\) 个 小黑子 的战斗力(Num_i <= 10^6)。

## 样例

输入

4
1 2 3 4


输出

26