凯萨用糖解决了问题,现在他正在回家的路上。
Caisa 一路上正在玩手机游戏。本游戏中有 (n + 1) 个编号从 0 到 n 的塔。编号为 0 的塔架高度为零,编号为 i (i > 0) 的塔架高度为 hi。游戏的目标是到达第 n 个塔,玩家唯一能做的动作就是从当前塔(将其编号记为 k)跳到下一个塔(其编号为 k + 1)。当玩家做出这样的举动时,其能量会增加 hk - hk + 1(如果该值为负,则玩家会损失能量)。玩家在任何时刻都必须拥有非负的能量。
最初,Caisa 站在 0 塔处,能量为 0。该游戏提供了一个特殊的机会:只需支付一美元即可将任何塔的高度增加一倍。凯萨可能会利用这个机会好几次,但他不想花太多钱。为了达到游戏目标他必须支付的最低金额是多少?
输入
第一行包含整数 n (1 ≤ n ≤ 105)。下一行包含 n 个整数 h1, h2, ..., hn (1 ≤ hi ≤ 105),表示塔的高度。
输出
打印一个数字,代表 Caisa 支付的最低金额。
示例
输入 #1
5 3 4 3 2 4
输出 #1
4
输入 #2
3 4 4 4
输出 #2
4
注意
在第一个样本中,他可以支付 4 美元,并将 0 号塔的高度增加 4 个单位。然后他就可以安全地通过最后一个塔塔了。