题目描述

导游丽贝卡想在杂志上宣传落基山脉。她拍了一张包含 $N$ 座山的照片，从左到右第 $i$ 座山的高度为 $h_i$。

她可以从照片左侧和右侧各裁去若干座山，也可以不裁去。裁剪后留下的是原照片中一段连续的山，即第 $l$ 座到第 $r$ 座山，其中 $l\le r$。她希望留下的照片尽可能对称。

我们用“不对称值”衡量一段照片的不对称程度：把距这段照片中点同样远的两座山配成一对，计算每对山高度差的绝对值，再把这些绝对值相加。

绝对值记为 $|v|$，例如 $|-6|=6$，$|14|=14$。区间 $[l,r]$ 的不对称值为

也就是说，从两端向中间依次配对，每对只计算一次。如果山的数量为奇数，中间那座山与自己配对，贡献为 $0$。

丽贝卡还不知道最终照片需要多宽。因此，对每一种可能的长度 $1,2,\ldots,N$，请分别求出：在所有保留该数量连续山峰的裁剪方案中，不对称值最小是多少。

输入格式

第一行一个整数 $N$，表示山的数量。

第二行 $N$ 个整数 $h_1,h_2,\ldots,h_N$，分别表示从左到右各座山的高度。

输出格式

输出一行 $N$ 个整数，用空格分隔。第 $i$ 个整数表示长度为 $i$ 的连续山峰片段中，最小的不对称值。

样例输入 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

1
1

样例输出 3

0

说明/提示

样例 1 解释

下面解释为什么第 $5$ 个输出值为 $2$。长度为 $5$ 的片段有三种：

• $[3,1,4,1,5]$：不对称值为 $|3-5|+|1-1|+|4-4|=2$。
• $[1,4,1,5,9]$：不对称值为 $|1-9|+|4-5|+|1-1|=9$。
• $[4,1,5,9,2]$：不对称值为 $|4-2|+|1-9|+|5-5|=10$。

三者中的最小值为 $2$。

样例 2 解释

这个样例满足子任务 2 的条件。唯一一个长度为 $4$ 的片段是 $[1,3,5,6]$，其不对称值为 $|1-6|+|3-5|=7$。

数据范围

本题采用捆绑测试。原比赛共 $15$ 分，各子任务如下：