1233: NOC000002 飞跃摩天轮

东东是一名超级英雄正在逃离坏人追捕，要在屋顶之间飞跃，最终到达安全的位置。逃跑路线一共有N座摩天大楼，从1到N进行编号，东东从1号大楼出发，通过特制的跳跃装置跳到2号大楼，然后再通过2号大楼跳到3号大楼……最终跳到N号大楼，就是目标的安全位置。由于跳跃距离越远，跳跃装置的安全性就越差，所以东东希望他跳跃的最距离尽可能小。为了安全，东东已经提前准备好两个强力热气球，热气球可以代替大楼作为东东一次跳跃的终点和下一次跳跃的起点，他可以把热气安排在合适的位置，来帮助他更安全的逃脱。

为了确定自己能顺利逃脱，东东需要他的技术顾问，也就是你，替他算出在最安全的情况下，他最大的跳跃距离。

【输入格式】

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

第二行为N个数表示每栋大楼之间的距离。

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

【输入样例1】

6

3 5 4 11 8

【输出样例1】

6

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

【输入样例2】

10

19 99 26 32 9 3 7 10 21

6

3 4 5 11 8

10
19 99 26 32 9 3 7 10 21

33