페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3869

스키장 디자인 1s 128MB

문제

정올이는 스키장을 건설하기 위해 산맥을 하나 통째로 구매했다.

해당 산맥에는 0부터 100 사이의 정수 높이를 가진 N개의 봉우리가 있다.

정식으로 스키장 개설을 하려면 정부의 안전규정을 준수하여야 하는데, 규정은 다음과 같다.

  • 스키장의 가장 낮은 봉우리의 높이를 L이라고 한다.

  • 스키장의 가장 높은 봉우리의 높이를 H라고 한다.

  • L과 H의 차이는 17 이하다.

문제는 공사비용이다. 각 봉우리별로 정수 x만큼의 높이를 바꿀 수 있는데, 높이를 높이거나 낮추기 위해서는 x^2만큼의 비용이 든다.

정올이가 안전규정을 지키기 위해서는 최소 얼마만큼의 공사비용을 소모해야 하는지 알아보자.


입력

첫 줄에 정수 N이 주어진다. (1 \le N \le 1,000)

두 번째 줄부터 N줄에 걸쳐 각 봉우리의 높이가 주어진다. 봉우리의 높이는 0부터 100 사이의 정수이다.


출력

첫 줄에 안전규정을 만족시킬 수 있는 최소 공사비용을 출력한다.


예제 

5
20
4
1
24
21
18

5개의 봉우리의 높이가 각각 1, 4, 20, 21, 24이다.

높이 4, 20, 21 의 봉우리는 그대로 두고, 높이 1짜리 봉우리를 높이 4로 만들고(cost = 3^2 = 9), 높이 24 봉우리를 높이 21로 낮추어 3^2 = 9의 추가 비용을 들이면 최소비용이다.



출처

USACO 2014 January Bronze
로그인해야 코드를 작성할 수 있어요.