나무

바이테아사르가 한 줄로 나무 $n$그루를 심었다. 키가 큰 나무와 작은 나무가 뒤섞여 있어 줄의 배치가 마음에 들지 않는다.

줄이 얼마나 어수선한지를 재기 위해 무질서 계수를 사용한다. 왼쪽부터 차례로 나무의 높이가 $h_1, h_2, \ldots, h_n$일 때, 무질서 계수는 다음과 같이 정의된다.

$|h_1 - h_2| + |h_2 - h_3| + \cdots + |h_{n-1} - h_n|$

이 값이 작을수록 줄이 더 가지런하다.

나무를 옮겨 심는 일은 힘들기 때문에 최대 두 그루만 옮긴다. 즉, 나무 두 그루를 골라 서로 위치를 바꾸거나(교환), 아무것도 바꾸지 않는다. 각 나무에 대해, 그 나무를 다른 한 그루와 교환했을 때 얻을 수 있는 가장 작은 무질서 계수를 구하라. 이때 어떤 나무도 옮기지 않고 그대로 두는 선택(교환하지 않음)도 허용된다.

나무들의 높이를 입력받아, 각 나무마다 그 나무를 다른 나무와 교환하거나 전혀 바꾸지 않았을 때 얻을 수 있는 가장 작은 무질서 계수를 출력하는 프로그램을 작성하라.

첫째 줄에 정수 $n$ ($2 \le n \le 50000$)이 주어진다.

둘째 줄에 나무들의 높이를 나타내는 $n$개의 정수 $h_1, h_2, \ldots, h_n$ ($1 \le h_i \le 10^8$)이 공백 하나로 구분되어 왼쪽부터 차례로 주어진다.

정확히 $n$개의 줄을 출력한다. $i$번째 줄에는 $i$번 나무를 옮겨 심는 경우(다른 한 그루와 교환하거나 그대로 두는 경우)를 고려했을 때 얻을 수 있는 가장 작은 무질서 계수를 정수 하나로 출력한다.

고정된 나무 $i$에 대한 선택지는 두 가지다. 줄 전체를 그대로 두거나, 나무 $i$를 다른 한 그루와 교환하는 것이다. 이 중 더 작은 무질서 계수를 출력한다.

첫 번째 예제에서 값 $7$은 나무 $1$과 $4$, 나무 $2$와 $5$, 또는 나무 $4$와 $5$를 교환하여 얻을 수 있다. 따라서 나무 $1$, $2$, $4$, $5$는 모두 $7$에 도달하고, 나무 $3$만은 $8$보다 더 줄일 수 없다.

두 번째 예제에서는 어떤 교환을 하더라도 계수가 커지므로, 모든 나무에 대해 아무것도 바꾸지 않는 것이 최선이며 각 답은 처음 계수인 $4$와 같다.