#104850. [BZOJ 4850] [Jsoi2016]灯塔

JSOI 的国境线上有 座连续的山峰，其中第 座的高度是 。为了简单起见，我们认为这 座山峰排成了连续一条直线。如果在第 座山峰上建立一座高度为 的灯塔，JYY 发现，这座灯塔能够照亮第 座山峰，当且仅当满足如下不等式：

JSOI 国王希望对于每一座山峰，JYY 都能提供建造一座能够照亮全部其他山峰的灯塔所需要的最小高度。你能帮助 JYY 么?

输入的第一行包含一个正整数 。

接下来 行，第 行包含一个正整数 ，表示第 座山峰的高度。

第 行包含一个非负整数，表示在第 座山峰上修建灯塔所需要的最小高度 。

输入样例

6
5
3
2
4
2
4

输出样例

2
3
5
3
5
4

对于 的数据，，。