대칭 산맥

레베카는 여행 가이드이며, 잡지에 실을 록키 산맥 사진을 찍었다. 그녀가 찍은 사진에는 $N$개의 산이 있고, 왼쪽에서 $i$번째 산의 높이는 $h_i$이다. 그녀는 잡지에 싣기 위해 사진의 왼쪽에서 산을 일부 잘라낼 수 있고, 오른쪽에서도 일부 잘라낼 수 있다. 즉, 자르기 결과는 $l$번째 산부터 $r$번째 산까지 연속된 산이며 $l \le r$이다. 레베카는 가장 대칭인 자르기를 찾고자 한다.

자르기의 비대칭 값은 모든 $0 \le i \le \frac{r-l}{2}$에 대해 $|h_{l+i} - h_{r-i}|$를 더한 값이다. 바깥쪽에서 중심을 향해 산을 짝지어 각 짝의 높이 차이 절댓값을 구하고, 이를 모두 더하면 된다.

레베카는 사진의 폭을 아직 정하지 못했다. 가능한 자르기 길이마다, 비대칭 값이 가장 작은 자르기의 비대칭 값을 구하라.

첫째 줄에 산의 개수 $N$이 주어진다. 둘째 줄에는 $N$개의 정수가 공백으로 구분되어 주어지며, $i$번째 정수는 $h_i$이다.

한 줄에 $N$개의 정수를 공백으로 구분하여 출력한다. $i$번째 정수는 길이가 $i$인 자르기 중 가장 대칭인 자르기의 비대칭 값이다.

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

$0 \le h_i \le 10^5$