P5503 [JSOI2016] 灯塔

`JSOI`的国境线上有$N$座连续的山峰,其中第$i$座的高度是$h_i$.为了简单起见,我们认为这$N$座山峰排成了连续一条直线.如果在第$i$座山峰上建立一座高度为$p(p≥0)$的灯塔,`JYY`发现,这座灯塔能够照亮第$j$座山峰,当且仅当满足如下不等式: $$h_j \le h_i+p-\sqrt {|i-j|}$$ `JSOI`国王希望对于每一座山峰,`JYY`都能提供建造一座能够照亮全部其他山峰的灯塔所需要的最小高度.你能帮助`JYY`么?

无

无

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