灯塔 ### 题目描述 `JSOI`的国境线上有$N$座连续的山峰,其中第$i$座的高度是$h_i$.为了简单起见,我们认为这$N$座山峰排成了连续一条直线.如果在第$i$座山峰上建立一座高度为$p(p≥0)$的灯塔,`JYY`发现,这座灯塔能够照亮第$j$座山峰,当且仅当满足如下不等式: $$h_j \le h_i+p-\sqrt {|i-j|}$$ `JSOI`国王希望对于每一座山峰,`JYY`都能提供建造一座能够照亮全部其他山峰的灯塔所需要的最小高度.你能帮助`JYY`么? ### 输入描述 输入一行包含一个正整数$N$。 接下来$N$行，第$i$行包含一个正整数$h_i$，表示第$i$座山峰的高度。 其中，$1< N \le 10^5,0 < h_i \le 10^9$。 ### 输出描述 第$i$行包含一个非负整数，表示在第$i$座山峰上修建灯塔所需要的最小高度$p_i$。 ### 输入输出样例 #### 示例 1 >输入 ``` txt 6 5 3 2 4 2 4 ``` >输出 ``` txt 2 3 5 3 5 4 ```