P3515 [POI 2011] Lightning Conductor

逐渐变化的气候迫使 Byteburg 当局建造一个巨大的避雷针，以保护城市内的所有建筑物。 这些建筑物沿着一条街道排成一行，编号从 $1$ 到 $n$。 建筑物和避雷针的高度是非负整数。 Byteburg 的资金有限，只能建造一个避雷针。 而且，正如你所料，避雷针越高，成本越高。 位于建筑物 $i$（高度为 $h_i$）屋顶上的高度为 $k$ 的避雷针可以保护建筑物 $j$（高度为 $h_j$），如果满足以下不等式： $$k + h_i \geq h_j + \sqrt{|i-j|}$$ 其中 $|i - j|$ 表示 $i$ 和 $j$ 之间的绝对差值。 Byteburg 的市长 Byteasar 请求你的帮助。 编写一个程序，对于每个建筑物 $i$，确定如果将避雷针放在建筑物 $i$ 上，能够保护所有建筑物的避雷针的最小高度。

标准输入的第一行有一个整数 $n$ ($1 \leq n \leq 500,000$)，表示 Byteburg 中的建筑物数量。 接下来的 $n$ 行中的每一行包含一个整数 $h_i$ ($0 \leq h_i \leq 1,000,000$)，表示第 $i$ 个建筑物的高度。

你的程序应输出恰好 $n$ 行到标准输出。 第 $i$ 行应给出一个非负整数 $k_i$，表示第 $i$ 个建筑物上避雷针的最小高度。

题面翻译由 ChatGPT-4o 提供。