时空限制

1S/512M

题目描述

定义跳跃操作：对数字 $x$ 进行参数为 $y$ 的跳跃操作，会将 $x$ 变为 $2\times y-x$。比如：对 $3$ 进行参数为 $1$ 的跳跃操作会变为 $-1$，对 $3$ 进行参数为 $4$ 的跳跃操作会变为 $5$，对 $3$ 进行参数为 $3$ 的跳跃操作会变为 $3$。

有 $n$ 个跳跃操作，编号为 $1\sim n$，编号 $i$ 的跳跃操作参数为 $a_i$。

初始数字 $x=0$，你选择一些（可以选 $0$ 个）跳跃操作，并按编号从小到大的顺序对 $x$ 依次进行这些跳跃操作，求最终 $x$ 最大是多少。

格式

输入格式

第一行包含一个整数 $n$，表示跳跃操作的数量。

第二行包含 $n$ 个整数 $a_i$，分别表示每个跳跃操作的参数。

输出格式

输出一个整数，表示最终 $x$ 的最大值。

样例

样例输入 #1

5
5 4 3 1 2

样例输出 #1

12

样例解释 #1

其中一种方案为依次进行编号为 $1,4,5$ 的跳跃操作，$x$ 的变化过程为：$0\Rightarrow 10\Rightarrow -8\Rightarrow 12$。

样例输入 #2

1
-2

样例输出 #2

0

样例输入 #3

11
1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000 1000000000

样例输出 #3

22000000000

数据规模

对于 $30\%$ 的数据，$n\leq 20$。

另有 $30\%$ 的数据，$n\leq 1000$，$-10\leq a_i\leq 10$。

对于 $100\%$ 的数据，$1\leq n\leq 10^5$，$-10^9\leq a_i\leq 10^9$。