题目描述

东东是一位穿梭在暗夜的城市里惩恶扬善的超级英雄，但是在一次侦查的过程中，他被一群坏蛋发现了。

为了逃脱恶人的追捕，东东需要在摩天楼的屋顶之间飞跃，最终到达安全的位置。逃跑路线一共有 $N$ 座摩天大楼，从1到 $N$ 进行编号，东东从1号大楼出发，通过特制的跳跃装置跳到2号大楼，然后再通过2号大楼跳到3号大楼…最终跳到$N$号大楼，就是目标的安全位置。由于跳跃距离越远，跳跃装置的安全性就越差，所以东东希望他跳跃的最大距离尽可能小。

为了安全，东东已经提前准备好两个强力热气球，热气球可以代替大楼作为东东一次跳跃的终点和下一次跳跃的起点，他可以把热气球安排在合适的位置，来帮助他更安全的逃脱。为了确定自己能顺利逃脱，东东需要他的技术顾问，也就是你，替他算出在最安全的情况下，他最大的跳跃距离。

输入格式

输入有两行，第一行为两个正整数 $N$，表示摩天大楼的数量。

第二行有 $N-1$个整数，表示第$i$座摩天大楼与第$i+1$座摩天大楼之间的距离。

输出格式

输出一个整数，表示东东最大的跳跃距离，如果结果是小数，请向上取整,

6
3 5 4 11 8

6

【样例1说明】 在第 4和第5座摩天大楼中间、第5和第6座摩天大楼中间各放一个热气球，东东可以进行次跳跃，距离分别是:3、5、4、5.5、5.5、4、4。其中最远距离向上取整为 6.

10
19 99 26 32 9 3 7 10 21

33

【数据范围】

对于 100% 的数据:$1≤N≤10^5$,相邻的摩天楼距离不超过$10^9$