SP9070 避雷针

气候变化使 Byteburg 不得不建造一个大型避雷针来保护城市里的所有建筑物。 这些建筑沿着一条街道排成一排，从 $1$ 到 $n$ 编号。 建筑物和避雷针的高度均为非负整数。Byteburg 有限的资金只允许建造一个避雷针。此外，避雷针越高，价格越贵。 在建筑物 $i$（高度为 $h_i$）屋顶放置高为 $p_i$ 的避雷针能够保护建筑物 $j$ 的条件是： $$ h_j\le h_i+p_i-\sqrt{\left| i-j\right|} $$ 其中 $\left| i-j\right|$ 表示 $i$ 和 $j$ 之间的差的绝对值。 Byteburg 需要你帮它计算，如果在第 $i$ 个建筑物的屋顶放置这样的避雷针的话，避雷针的最小高度是多少。

第一行一个整数 $n(1\le n\le 5×10^5)$ 表示 Byteburg 的建筑物个数。 接下来 $n$ 行每行一个整数 $h_i(0\le h_i\le 10^9)$ 表示第 $i$ 个建筑物的高度。

输出 $n$ 行，每行一个非负整数 $p_i$ 表示第 $i$ 个建筑物屋顶上放置避雷针的最小高度。

由 @Chlero 提供翻译