#2074. 「JSOI2016」灯塔

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

如果在第 i 座山峰上建立一座高度为 p\ (p \geq 0) 的灯塔,JYY 发现,这座灯塔能够照亮第 j 座山峰,当且仅当满足如下不等式:

h_j \leq h_i+p-\sqrt{|i−j|}

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

输入格式

输入第一行为一个整数 N ,代表山峰的数目。
接下来 N 行,每行一个数 h_i ,代表第 i 座山峰的高度是 h_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