题目描述

小爱在参加一个跑步比赛，比赛路线分为 $n$ 段，其中第 $i$ 段的分数为 $a_i$。在每段路上，小爱可以选择跑步、突击或慢走，每种方式得分不同，具体规则如下：

• 如果在一段路上选择跑步，可以得 $a_i$分；
• 如果在一段路上选择突击，分数会加倍，变成 $2a_i$ 分，但下一段路就只能慢走了；
• 如果在一段路慢走，得分为 $0$。

小爱在每段路上应该如何选择，才能使得分之和最大呢？

输入格式

第一行：单个整数 $n$。 第二行：$n$ 个整数表示 $a_1$ 到 $a_n$。

输出格式

单个整数：表示答案。

4
1 2 3 4

14

样例解释 1

前几段都正常跑步，最后一段突击，得分为1+2+3+4*2

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 100$；
• 对于 $60\%$ 的数据，$1\leq n\leq 1000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 100000$； $1\leq a_i\leq 10000$。