스키장 디자인

정올이는 스키장을 건설하기 위해 산맥을 하나 통째로 구매했다. 해당 산맥에는 N개의 봉우리가 있다.

각 i번째 봉우리의 높이는 H_i이다.

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

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

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

입력

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

두 번째 줄부터 N줄에 걸쳐 H_i가 주어진다. (0 \le H_i \le 100)

출력

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

예제1

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

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

출처

USACO 2014 January Bronze

스키장 디자인 1000초 128MB