题目描述

JSOI的国境线上有$N$座连续的山峰,其中第$i$座的高度是$h_i$.为了简单起见,我们认为这$N$座山峰排成了连续一条直线.如果在第$i$座山峰上建立一座高度为$p(p≥0)$的灯塔,JYY发现,这座灯塔能够照亮第$j$座山峰,当且仅当满足如下不等式:

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

输入格式

输入一行包含一个正整数$N$。

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

输出格式

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

6
5
3
2
4
2
4

2
3
5
3
5
4

提示

对于$100\%$的数据，$1< N \le 10^5,0 < h_i \le 10^9$