캥거루 파티

면접 대비

시간 제한1초메모리 제한512 MB

요약

서로 다른 n개의 집 위치가 주어질 때, 두 집을 파티 장소로 골라 모든 집에서 가장 가까운 파티 장소까지의 거리 제곱 합이 최소가 되도록 한다.

문제

수직선 위의 집들에 캥거루 무리가 살고 있다. 모두 캥거루 볼을 보고 싶어 한다!

캥거루가 한 집에 다 들어갈 수 없으므로, 두 마리를 정해 각자의 집에서 파티를 열게 한다. 나머지 캥거루는 모두 자신에게 가장 가까운 집으로 가며, 두 집까지의 거리가 같으면 아무 쪽이나 고른다.

캥거루가 위치 $a$ 에서 위치 $b$ 로 이동할 때 $(a - b)^2$ 만큼의 에너지를 쓴다. 파티를 열 두 집의 위치를 최적으로 정했을 때, 모든 캥거루가 쓰는 에너지의 최솟값을 구하시오.

첫째 줄에 캥거루의 수 $n$ ( $2 \le n \le 50$ )이 주어진다.

다음 $n$ 개 줄에 각각 정수 $x$ ( $-1,000 \le x \le 1,000$ )가 주어지며, 이는 캥거루 한 마리의 집이 수직선 위에 있는 위치이다. 모든 위치는 서로 다르다.

파티를 열 두 집의 위치를 최적으로 정했을 때 모든 캥거루가 쓰는 에너지의 최솟값을 한 줄에 출력한다.