题目描述

佩奇经常和同学玩一个一维数组游戏:

对于一个给定的一维数组,数组中的每个元素$a_i$均为非负整数.

1.每次从数组的第一个或者是最后一个位置取走一个元素

2.每次取数有一个的分值,得分=被取走的元素$\times 2^i$,其中$i$表示第$i$次取数(从1开始)

佩奇请你帮忙写一个程序，对于任意数组，可以求出取数后的最大得分。

输入

第一行输入一个整数$n$

第二行一共有$n$个元素

输出

对于任意数组，可以求出取数后的最大得分。

3
1 2 3

34

提示

$1 \leq n \leq 50$

$0 \leq 数组中的元素 \leq 100$