题面描述：

多多正在玩一个一维数轴上的传送门游戏。游戏开始时，他位于 $x = 0$ 位置，一共有 $n$ 个传送门依次可用（顺序为 $1$ 到 $n$，不能更改使用顺序）。第 $i$ 个传送门有一个传送值 $a_i$，当多多使用该传送门时，会将他的当前位置 $x$ 改变为 $x + a_i$。传送门是一次性的，用过就不能再用。

此外，多多拥有一次“反转”技能，可以在任意时刻将当前位置从 $x$ 变为 $-x$，该技能至多只能使用一次（也可选择不用）。当多多先后使用完 $1$ 到 $n$ 号传送门后，我们想知道在整个传送/反转的过程中，多多与初始位置（$0$ 点）之间的最大距离是多少（即最大值 $\max |x|$）。

思路与详细解析

题目内容

多多在玩一个传送门游戏。

游戏开始时多多在一维数轴的$x=0$处。他有$n$个传送门，每个传送门都有一个传送值$a_i$，他能

使用该传送门从$x=t$位置传送到$x=t+a_i$，传送门是消耗品，只能使用一次。同时他还有一 个“反转”技能，使用该技能可以立即从位置$x=t$“反转”到$x=-t$.

多多必须从$1$到$n$使用这些传送门，可以在任何时候使用“反转”技能(最多用一次，也可以不 用)，问用完所有传送门后，多多到初始位置$x=0$最远的距离为多少?

输入描述

第一行为一个正整数$n(1≤n≤10^5)$，

第二行为$n$个整数 $a_1,a_2,….,a_n (-10^9≤a_i≤10^9)$。

输出描述

输出在传送的过程中，多多到初始位置距离的最大值。

补充说明

对于 $60$ 的数据,$1≤n≤1000$;

对于100% 的数据，$1≤n≤10^5,-10^9≤a_i≤10^9$.

样例1

输入

4
1 1 -1 1

输出

3

说明

最初多多在位置$x=0$处;

他先依次使用第$2$个传送门，到达位置$x=0+a_1+a_2=0+1+1=2$，与初始位置距离为$2$

然后他使用技能“反转”，到达位置$x=-2$，与初始位置距离为$2$;

再使用第$3$个传送门，到达位置$x=-2+a_3=-2-1=-3$，与初始距离为$3$;

最后使用第$4$个传送门，到达位置$x=-3+a_4=-3+1=-2$,与初始位置距离为$2$

在传送的过程中，与初始位置距离最大为3.

样例2

输入

5
1 -4 10 -30 2

输出

37

说明

多多在使用过前$3$个传送门后到达$x=7$;

此时使用一次“反转”，到达$x=-7$;

再使用第$4$个传送门到达$x=-37$，此时与初始位置距离最远，为$37$。