Symmetric Mountains

Interview

Time limit1sMemory limit1024 MB

Summary

For each crop length, finds the minimum sum of height differences between mirrored mountain pairs over all consecutive crops of that length.

Level: Medium4 of 10
Topics: Brute force, Array
Solved: No attempts yet

Problem

Rebecca is a tour guide and is trying to market the Rocky Mountains for her magazine. She recently took a picture of $N$ mountains, where the $i$ -th mountain from the left has height $h_i$ . She will crop this picture for her magazine by possibly removing some mountains from the left side and possibly removing some mountains from the right side. A crop consists of consecutive mountains from the $l$ -th to the $r$ -th mountain, where $l \le r$ . Rebecca wants the most symmetric crop.

The asymmetric value of a crop is the sum of $|h_{l+i} - h_{r-i}|$ for all $0 \le i \le \frac{r-l}{2}$ . In other words, pair the mountains from the outside in toward the center, compute the absolute height difference of each pair, and add them up.

Rebecca does not know how wide the picture needs to be. For every possible crop length, find the asymmetric value of the most symmetric crop, which is the crop with the minimum asymmetric value.

Input

The first line contains an integer $N$ , the number of mountains. The second line contains $N$ space-separated integers, where the $i$ -th integer is $h_i$ .

Output

Print on one line $N$ space-separated integers. The $i$ -th integer is the asymmetric value of the most symmetric crop of length $i$ .

Constraints

$1 \le N \le 5\,000$

$0 \le h_i \le 10^5$

Examples2

Example 1
Input
```
7
3 1 4 1 5 9 2
```
Expected output
```
0 2 0 5 2 10 10
```
Example 2
Input
```
4
1 3 5 6
```
Expected output
```
0 1 3 7
```