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 么？

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

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

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