描述

2022NOC 初中组 C++ 选拔赛，第三题

东东是一位穿梭在暗夜的城市里惩恶扬善的超级英雄，但是在一次侦查的过程中，他被一群坏蛋发现了。为了逃脱恶人的追捕，东东需要在摩天楼的屋顶之间飞跃，最终到达安全的位置。逃跑路线一共有 N 座摩天大楼，从 1 到 N 进行编号，东东从 1 号大楼出发，通过特制的跳跃装置跳到 2 号大楼，然后再通过 2 号大楼跳到 3 号大楼…最终跳到 N 号大楼，就是目标的安全位置。由于跳跃距离越远，跳跃装置的安全性就越差，所以东东希望他跳跃的最大距离尽可能小。为了安全，东东已经提前准备好两个强力热气球，热气球可以代替大楼作为东东一次跳跃的终点和下一次跳跃的起点，他可以把热气球安排在合适的位置，来帮助他更安全的逃脱。为了确定自己能顺利逃脱，东东需要他的技术顾问，也就是你，替他算出在最安全的情况下，他最大的跳跃距离。

格式

输入

输入有两行，第一行为两个正整数 N，表示摩天大楼的数量。 第二行有 N−1 个整数，表示第 i 座摩天大楼与第 i+1 座摩天大楼之间的距离。

输出

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

输入输出样例

6
3 5 4 11 8

6

限制

1秒, 1024KiB 测试内存.