C. 严神的机器人 III

严神这次把机器人用来跳房子。

直线上有 幢房子， 编号为 。其中第 幢的高度为 . 机器人最初在1号房子上，初始能量为 ， 它只能从第 幢房子跳到第 幢。 当机器人跳动的时候，它所具有的能量将先翻倍再减去落地时房子的高度。

严神知道， 他的机器人在任何时候能量不能为0或负， 否则， 机器人将停止工作。 他唯一能调节的是初始能量 . 他想知道， 至少需要给多少初始能量才能使它成功跳到n号房子处。

输入共 2 行。

第 1 行， 一个整数 , 房子的数量。

第 2 行， 个整数， 代表各个房子的高度。

输出仅一行一个整数， 最小所需初始能量。

样例输入 1

5
1 3 2 4 5

样例输出 1

3

本题采用捆绑测试。 当通过子任务所有数据点后方可获得该任务的分数。

对于所有数据， .