Description

某个比赛分为n段，其中第i段的分数为ai​。在每段路上，可以选择正常、加速或减速，每种方式得分不同，具体规则如下：

• 如果在一段选择正常，可以得ai​分；
• 如果在一段选择加速，分数会加倍，变成2*ai​分，但下一段就只能减速了；
• 如果在一段减速，得分为0。

应该如何选择，才能使得分之和最大。

Input Format

第一行：单个整数n。

第二行：n个整数表示a1​到an​。

Output Format

单个整数：表示答案。

4
1 2 3 4

14

Hint

对于30%的数据，1≤n≤100;

对于60%的数据，1≤n≤1000；

对于100%的数据，1≤n≤100000；

1≤ai≤10000。

Source