일직선상에 N개의 전봇대가 한 줄로 서있다.

편의상, 일직선을 x-축이라 하고, 전봇대가 서 있는 위치 x₀, x₁, ..., x_N-1은 x-축 상의 x-좌표라고 하자.

x₀는 항상 0이고 x_i(i≥1)는 양의 정수라고 가정한다.

이 전봇대들을 이웃한 두 전봇대 사이의 거리가 모두 일정하도록 일부 전봇대들을 옮기려고 한다.

이때 이동해야하는 전봇대들의 거리의 합이 최소가 되도록 해야 한다.

단, x₀에 위치한 전봇대는 움직일 수 없고, 이동하는 전봇대들은 정수 좌표 위치로만 이동 가능하다.

예를 들어, 아래의 그림 1과 같이 전봇대가 주어져 있다고 하자.

이 경우 그림 2에서와 같이 x-좌표 6과 9에 위치한 전봇대를 각각 x-좌표 8과 12인 곳으로 이동하면,

모든 이웃한 전봇대들의 거리는 4로 같고 전봇대의 이동 거리의 합은 5이다.

하지만 그림 3과 같이 x-좌표 4에 위치한 전봇대만을 x-좌표 3인 곳으로 이동하면,

이웃한 전봇대들의 거리는 모두 3이고 전봇대의 이동 거리의 합은 1이다.

전봇대들의 위치 x₀, x₁, ..., x_N-1이 주어지면, 모든 이웃한 전봇대들의 거리가 같도록 전봇대들을 이동할 때(x₀에 위치한 전봇대는 고정), 이동거리의 합이 최소가 되도록 하는 프로그램을 작성하시오.

전봇대 timer 1초 memory 32MB

전봇대 1초 32MB