题目描述

小宇是一位天文爱好者，最近他用自己的望远镜拍摄了一张横跨 $N$ 颗恒星的星图。每颗恒星在星图上的亮度被记录为一个整数亮度值 $h_i$，这些恒星在图中按从左到右依次排列。

小宇想要从中裁剪出一段连续的恒星序列，作为自己的星图收藏。为了让画面更具美感，他希望这段被裁剪的星图尽可能对称。这意味着，裁剪出的星图在视觉上应左右平衡，即中心对称。

为了评估“对称性”，我们定义一个裁剪片段的不对称值如下：

对于一个包含从第 $l$ 颗恒星到第 $r$ 颗恒星（$l \le r$）的片段，设它的中心对称轴位于中点，每对等距于中点的恒星，其亮度差的绝对值记为 $|h_{l+i} - h_{r-i}|$，其中 $0 \le i \le \frac{r - l}{2}$。

所有这样的差值求和即为该片段的不对称值。

小宇想在所有可能的裁剪片段中，找出一个不对称值最小的片段，来作为他最完美的星图剪辑。

输入格式

第一行包含一个整数 $N$，表示恒星的总数量。

第二行包含 $N$ 个用空格分隔的整数 $h_i$，表示每颗恒星的亮度值，按从左到右顺序排列。

输出格式

输出一行 $N$ 个整数，第 $i$ 个整数表示长度为 $i$ 的裁剪中最小的不对称值。

数据范围

对于 30% 的数据，$N\leq 300$ 。

对于另外 40% 的数据，恒星的亮度值从左到右单调不减。

对于 100% 的数据，$1\leq N\leq 5000,0\leq h_i\leq 10^5$ 。

输入输出样例

输入样例1

7
3 1 4 1 5 9 2

输出样例1

0 2 0 5 2 10 10

输入样例2

4
1 3 5 6

输出样例2

0 1 3 7

输入/输出样例3

见下发文件。