测试数据来自 system/1175

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　对于一个给定的长度为 \(n\) 的整数序列 \(a_1,a_2,…,a_n\)，每个元素 \(a_i\) 为非负整数。游戏规则如下：
　　1、每次须从序列中取走一个元素，共取 \(n\) 次；
　　2、每次取走的元素只能是当前序列的首或尾元素；
　　3、每次取数的得分 = 被取走的元素值\(*2^r\)，其中 \(r\) 表示第 \(r\) 次取数（从 \(1\) 开始编号）；
　　4、游戏结束总得分为 \(n\) 次取数得分之和。
　　请你写一个程序计算对于任意序列取数后的最大得分。

【输入格式】

　　第一行一个整数 \(n\)，表示整数序列的长度。
　　第二行有 \(n\) 个用空格分开的非负整数，表示整数序列：\(a_1,a_2,…,a_n\)。

【输出格式】

　　一个整数，表示最大得分。

【输入输出样例】

　Input

4
4 5 0 5

　Output

122

【数据限制】

　　\(n \le 60，0 \le a_i \le 1000\)

【来源】

　　Mr.he