P3515 [POI 2011] Lightning Conductor

日益加剧的气候变化迫使比特堡当局建造一座巨大的避雷针，用以保护城中的所有建筑。这些建筑沿着同一条街道排成一列，依次编号为 $1$ 到 $n$。 建筑的高度和避雷针的高度均为非负整数。比特堡有限的预算只允许建造**一座**避雷针。当然，避雷针建得越高，造价也就越高。 若一座高度为 $p$ 的避雷针安装在建筑 $i$（高度为 $h_i$）的屋顶，且对于建筑 $j$（高度为 $h_j$）满足以下不等式，则该避雷针能够保护建筑 $j$： $$h_j \le h_i + p - \sqrt{|i - j|}$$ 其中 $|i - j|$ 表示 $i$ 与 $j$ 之差的绝对值。 比特堡的市长比特萨尔请求你的帮助。请编写一个程序，对于每一栋建筑 $i$，计算出如果将避雷针安装在该建筑顶部，能够保护**全部**建筑所需的最小避雷针高度。

第一行包含一个整数 $n$ ($1 \le n \le 500\,000$)，表示比特堡的建筑数量。 接下来的 $n$ 行，每行包含一个整数 $h_i$ ($0 \le h_i \le 1\,000\,000\,000$)，表示第 $i$ 栋建筑的高度。

你的程序应输出恰好 $n$ 行。第 $i$ 行应输出一个非负整数 $p_i$，表示安装在第 $i$ 栋建筑上的避雷针的最小高度。

题面翻译由 DeepSeek V4 Pro 提供。