3015: 灯塔

内存限制:125 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:7 通过:2

题目描述

https://loj.ac/p/2074

JSOI 的国境线上有 N 座连续的山峰,其中第 i 座的高度是 hi 。为了简单起见,我们认为这 N 座山峰排成了连续一条直线。

山峰与灯塔高度均为非负整数。如果在第 i 座山峰上建立一座高度为 p(p>=0)  的灯塔,JYY 发现,这座灯塔能够照亮第 j 座山峰,当且仅当满足如下不等式:

                                  

                                    hj<=hi+p-sqrt(|i-j|)

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



输入格式

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


输出格式

输出  N 行,表示每座山峰需要建造的灯塔高度  pi
1<=N<=105, 0<hi<=109


输入样例 复制

6
5
3
2
4
2
4

输出样例 复制

2
3
5
3
5
4