分数: 400 分
问题陈述
高桥正在爬山。路线分为 N 部分,高桥当前的高度最初是 0.
当经过 i- 第节 (i = 1, 2, \ldots, N),高度变化 D_i (正 D_i 表示升序,负数表示降序, 0 表示平坦)。但是,海拔高度始终为非负值,如果改变后的海拔高度为负值,则变为 0。也就是说,如果经过之前的高度是 h,经过后的海拔高度变为 \max(h + D_i,\ 0).
为了保存能量,高桥必须使用 索道正好一次 攀爬期间。使用索道时,当前海拔高度 h 立即更改为 \lfloor h / 2 \rfloor (除以得到的值 h by 2 并向下舍入)。
索道可在以下任一地点使用 N + 1 点:
- 第 1 部分之前
- 之间 i第节和 (i+1)- 第节 (i = 1, 2, \ldots, N-1)
- 之后 N第节
高桥想在完成所有任务后将他的高度降到最低 N 路段并使用索道。求出在最佳时机使用索道时可能的最小最终高度。
约束
- 1 \leq N \leq 5 \times 10^5
- -10^9 \leq D_i \leq 10^9
- 所有输入均为整数。
输入
N D_1 D_2 \ldots D_N
- 第一行包含一个整数 N 代表节数。
- 第二行包含 N 整数 D_1, D_2, \ldots, D_N 以空格分隔,代表每个部分的海拔高度变化。
输出
在一行中打印索道在最佳时间仅使用一次时可能的最小最终高度。
示例输入 1
5 3 4 -2 5 -6
示例输出 1
0
示例输入 2
4 -5 10 -3 2
示例输出 2
4
示例输入 3
12 8 -3 15 -20 7 0 12 -5 -30 25 -4 6
示例输出 3
13
示例输入 4
30 100 -40 25 -200 300 -150 0 80 -30 60 -500 400 10 -20 35 -5 -5 90 -100 250 -60 70 -10 -400 500 -250 125 -75 30 -15
示例输出 4
192
示例输入 5
1 1000000000
示例输出 5
500000000