题解

题面描述

多多在一维数轴上玩一个“传送门”游戏：

• 初始位置在 $x = 0$。
• 有 $n$ 个传送门，每个传送门有一个“传送值” $a_i$，可将当前位置 $t$ 传送至 $t + a_i$。
• 每个传送门只能使用一次，可以按任意顺序使用这些传送门。
• 多多还拥有一个**“反转”技能**，可将位置从 $x = t$ 立刻变为 $x = -t$。该技能最多使用一次，也可以选择不使用。

题目内容

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

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

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

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

输入描述

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

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

输出描述

输出用完所有传送门后，多多到初始位置距离的最大值。

补充说明

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

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

样例1

输入

4
1 -2 3 -4

输出

0 1 2 4 4 

说明

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

他先选择使用第$2,4$个传送门，到达位置$x=0+a_2+a_4=0-2-4=-6$;

然后他使用技能“反转”，到达位置$x=6$;

最后选择第$1,3$个传送门，到达位置$x=6+a_1+a_3=6+1+3=10$，与初始位置距离最大为$10$。