题目描述

JSOI 的国境线上有 $N$ 座连续的山峰，其中第 $i$ 座的高度是 $h_i$。我们认为这 $N$ 座山峰排成了一条直线。

如果在第 $i$ 座山峰上建立一座高度为 $p$（$p \geq 0$）的灯塔，这座灯塔能够照亮第 $j$ 座山峰，当且仅当满足如下不等式：

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

输入格式

输入第一行为一个整数 $N$，代表山峰的数目。
接下来 $N$ 行，每行一个数 $h_i$，代表第 $i$ 座山峰的高度。

输出格式

输出 $N$ 行，表示每座山峰需要建造的灯塔高度 $p_i$。

样例

输入

6
5
3
2
4
2
4

输出

2
3
5
3
5
4

数据范围与提示

对于所有数据：

• $1 < N \leq 10^5$
• $0 < h_i \leq 10^9$