持续的气候变化迫使 Byteburg 当局建造一个巨大的避雷针，以保护城中所有的建筑物。这些建筑物沿一条街道排成一行，编号从 $1$ 到 $n$。

建筑物和避雷针的高度均为非负整数。由于资金有限，Byteburg 只能建造一个避雷针。此外，正如预期的那样，避雷针越高，造价就越昂贵。

若将高度为 $p$ 的避雷针安装在第 $i$ 号建筑物（高度为 $h_i$）的屋顶上，则该避雷针能够保护第 $j$ 号建筑物（高度为 $h_j$）的条件是满足以下不等式：

$$ h_j \le h_i + p - \sqrt{\lvert i - j \rvert} $$

其中 $\lvert i-j \rvert$ 表示 $i$ 与 $j$ 之差的绝对值。

Byteburg 市长 Byteasar 请求你的帮助。请编写一个程序，对于每一栋建筑物 $i$，计算若将避雷针安装在第 $i$ 号建筑物上，能够保护所有建筑物所需的最小避雷针高度。

输入格式

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

输出格式

你的程序应向标准输出打印恰好 $n$ 行。第 $i$ 行应输出一个非负整数 $p_i$，表示安装在第 $i$ 号建筑物上的避雷针所需的最小高度。

样例

输入 1

6
5
3
2
4
2
4

输出 1

2
3
5
3
5
4