配点 : 500 点
問題文
如果整数是 1 一张一张写的卡片 N 纸张从顶部开始堆叠。 i 第二个是 写入 a_{i} 。
Alice 和 Bob 决定使用这些卡片玩游戏。
2 人们从爱丽丝开始,轮流从顶部拿起剩余的卡片。 1 取多少块,记下此时取的整数之和。
当没有剩余牌时,使用写出的整数计算本场比赛的分数。
写出的整数个数为 K 从最小的开始 本场比赛的得分为大于或等于 (K+1)/2 的最小整数。
2 该人事先知道卡上写的号码。 Alice想让游戏得分尽可能高,而Bob则想让游戏得分尽可能小。
2 当大家都发挥最好的时候,这场比赛的得分是多少?
制約
- 1 \leq N \leq 1000
- 0 \leq |a_i| \leq 10^9
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N
a_1 a_2 ... a_{N-1} a_N
出力
2 当该人做出最佳投注时打印游戏得分。
入力例 1
2 1 -1
出力例 1
1
爱丽丝第一 如果我们取 \{1, -1\} ,写入的整数是 \{0\} 得分为 0 。 爱丽丝第一 采取 \{1\} ,鲍勃有 \{-1\} 写入的整数是 \{1, -1\} 得分为 1 。
因此,对于爱丽丝 最好选择 \{1\} ,分数为 1 。
入力例 2
3 3 1 4
出力例 2
8