[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`么?

输入一行包含一个正整数$N$。 接下来$N$行，第$i$行包含一个正整数$h_i$，表示第$i$座山峰的高度。

第$i$行包含一个非负整数，表示在第$i$座山峰上修建灯塔所需要的最小高度$p_i$

6
5
3
2
4
2
4

2
3
5
3
5
4

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