USACO2014 铜组第一题

题目描述

农夫约翰（Farmer John）的农场里有 ( N ) 座山丘（( 1 <= N <= 1000 )），每座山丘的海拔是介于 ( 0 ) 到 ( 100 ) 之间的整数。在冬季，由于这些山丘上降雪充足，约翰会定期开办滑雪训练营。

不幸的是，约翰刚得知明年将对用作滑雪训练营的农场征收新税。不过，在仔细研读法规后，他发现“滑雪营地”的官方定义要求，营地上最高山丘和最低山丘的海拔差必须严格大于 17。因此，他可以通过降低最高山丘的高度，或者垫高较矮山丘的高度，使得调整后最高与最低山丘的海拔差至多为 17，从而避免缴税。

调整一座山丘的海拔，每改变 ( x ) 单位高度，花费为 ( x^2 ) 货币单位。现在要计算约翰调整山丘海拔，使最高与最低海拔差至多为 17 所需的最小花费。并且约翰只能将每座山丘的海拔调整整数单位。

输入格式

• 第 1 行：整数 ( N )（山丘的数量）。
• 第 2 至 ( N + 1 ) 行：每行一个整数，表示一座山丘的海拔。

输出格式

输出 1 行，为调整后最高与最低海拔差至多为 17 时，所需的最小花费。

样例输入

5
20
4
1
24
21

输入详情

农夫约翰的农场有 5 座山丘，海拔分别为 1、4、20、21、24。

样例输出

样例输出

18

输出详情

约翰保留海拔为 4、20、21 的山丘不变。他将海拔 1 的山丘垫高到 4（花费 ( 3^2 = 9 ) ），将海拔 24 的山丘降低到 21（花费 ( 3^2 = 9 ) ）。总花费 ( 9 + 9 = 18 )。

说明/提示

无额外说明，按题目规则和样例逻辑处理即可。数据范围等约束见题目原文描述。