由于zhongshi太聪明了，jacky_hu决定自己出一道题目。

题目背景：

话说上次经过家鸡王国经过顽强抵抗，终于没有被灭国。宓果哪里肯善罢甘休，他心有不甘，继续向家鸡王国展开攻击。
宓果知道，因为自己身旁便有一个科技强国中士国，继续下去的局面对自己肯定是不利的。他要积极发展自己的文化，学习帝国主义制度，增强自己的国力。
于是，宓果找到了会编程的你，希望你帮帮他。

题目描述：

宓果王国是一个集合生产，艺术和科学为一体的强国，它不只注重发展文教事业，而且发展自己的军事实力，最重要的是，宓果王国是最早(?)进入上古时期（啊不是）的王国。
宓果王国深知，继续发展是很慢的，他想保持自己的优势，于是它研究出一种究极大法，那就是————分离与合体！
宓果王国有n个艺人，每个的文化产出不一样，为\(a_i\)，这天他们站成了一排。
宓果可以将两个相邻的艺人合并成同一个艺人，增加两倍的文化产出。
于是宓果问你如何才能让自己的文化产出最大化？

输入格式：

第1行：一个整数，表示n。
第2至n+1行：一行一个整数，表示\(a_i\)。

输出格式：

一行，一个整数，表示文化产出的最大值。

输入样例:

4
4 5 9 4

输出样例：

54

提示：

数据不会卡你，正常做就行。