AT_arc189_d.[ARC189D] Takahashi is Slime

有 $N$ 个史莱姆排成一列，从左到右依次编号为 $1, 2, \ldots, N$。第 $i$ 个史莱姆的大小为 $A_i$。
对于每一个位置 $K = 1, 2, \ldots, N$，解决下面的问题：

初始时，第 $K$ 个史莱姆是高桥君。高桥君可以执行任意多次（可以是 $0$ 次）的操作。请计算高桥君在操作后能达到的最大大小。

• 高桥君可以吸收一个相邻且大小小于他的史莱姆。吸收后，该史莱姆消失，高桥君的大小增加该史莱姆的大小。

在这个过程中，被吸收的史莱姆消失后空出的位置会立即由两侧的史莱姆填补，这使得两端的史莱姆重新相邻（请参考样例 1）。

从标准输入读取以下格式的数据：

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

对于每个 $K = 1, 2, \ldots, N$，输出问题的答案 $B_K$，各答案以空格分隔：

$B_1$ $B_2$ $\ldots$ $B_N$

• $2 \leq N \leq 5 \times 10^5$
• $1 \leq A_i \leq 10^9$
• 所有输入都是整数

样例解释

以 $K = 4$ 为例。我们用方括号 [] 标识高桥君，称其为列状态。初始状态下的列为 $(4, 13, 2, [3], 2, 6)$。以下是高桥君的操作步骤：

1. 高桥君吸收右邻的史莱姆，大小变为 $3 + 2 = 5$，列状态变为 $(4, 13, 2, [5], 6)$。
2. 高桥君吸收左邻的史莱姆，大小变为 $5 + 2 = 7$，列状态变为 $(4, 13, [7], 6)$。
3. 高桥君吸收右邻的史莱姆，大小变为 $7 + 6 = 13$，列状态变为 $(4, 13, [13])$。

最终，高桥君再也无法吸收任何比他小的邻居，所以他的最大可能大小是 $13$。

本翻译由 AI 自动生成