Description

逐渐变化的气候迫使 Byteburg 当局建造一个巨大的避雷针，以保护城市内的所有建筑物。

这些建筑物沿着一条街道排成一行，编号从 $1$ 到 $n$。

建筑物和避雷针的高度是非负整数。

Byteburg 的资金有限，只能建造一个避雷针。

而且，正如你所料，避雷针越高，成本越高。

位于建筑物 $i$（高度为 $h_i$）屋顶上的高度为 $k$ 的避雷针可以保护建筑物 $j$（高度为 $h_j$），如果满足以下不等式：

其中 $|i - j|$ 表示 $i$ 和 $j$ 之间的绝对差值。

Byteburg 的市长 Byteasar 请求你的帮助。

编写一个程序，对于每个建筑物 $i$，确定如果将避雷针放在建筑物 $i$ 上，能够保护所有建筑物的避雷针的最小高度。

Input Format

标准输入的第一行有一个整数 $n$ ($1 \leq n \leq 500,000$)，表示 Byteburg 中的建筑物数量。

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

Output Format

你的程序应输出恰好 $n$ 行到标准输出。

第 $i$ 行应给出一个非负整数 $k_i$，表示第 $i$ 个建筑物上避雷针的最小高度。

6
5
3
2
4
2
4

2
3
5
3
5
4

Hint

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