Symmetric Mountain Crop

Rebecca is a tour guide and is trying to market the Rocky Mountains for her magazine. She recently took a beautiful picture consisting of \(N\) mountains where the \(i\text{-th}\) mountain from the left has a height \(h_i\). She will crop this picture for her magazine, by possibly removing some mountains from the left side of the picture and possibly removing some mountains from the right side of the picture. That is, a crop consists of consecutive mountains starting from the \(l\text{-th}\) to the \(r\text{-th}\) mountain where \(l \leq r\). To please her magazine readers, Rebecca will try to find the most symmetric crop.

We define the asymmetric value of a crop as the sum of \( |h_{l+i} - h_{r-i}| \) for every \(i\) such that \(0 \leq i \leq \lfloor (r-l)/2 \rfloor\). In other words, we pair up the mountains from the outside in toward the centre, calculate the absolute difference in height of each pair, and sum them up.

For each possible crop length, i.e. for every value of \(L = r-l+1\) (from \(1\) to \(N\)), find the minimum asymmetric value among all crops of that length.

inputFormat

The input consists of two lines. The first line contains an integer (N) denoting the number of mountains. The second line contains (N) space-separated integers (h_1, h_2, \ldots, h_N) representing the heights of the mountains.

outputFormat

Output a single line containing (N) space-separated integers, where the (i)-th integer denotes the minimum asymmetric value among all crops of length (i).

sample

3
1 2 3

0 1 2