4027 - 羊村大会

题目描述

在宁静的羊村,有 N 只小羊,它们的家都建在一条笔直的乡间小路旁。第 i 只小羊的家位于坐标 X_i 的位置。

现在,小羊们准备召开一年一度的羊村大会,商讨关于牧草分配和栅栏修建等重要事情。大会必须在这条小路上的某个整数坐标位置举行,所有小羊都要到场。

如果大会在坐标 P 举行,那么第 i 只小羊需要消耗的体力值为 (X_i - P)^2

请你编程计算,如果选择合适的整数坐标位置举行羊村大会,使得所有小羊们的总体力消耗最小,那么这个最小值是多少?

输入

1 行读入一个整数 N,表示有 N 只小羊。

2 行读入 N 个整数 X_1, X_2, ..., X_N,表示每只小羊家的坐标。

输出

输出一个整数,表示所有小羊参加羊村大会的最小总体力消耗。

样例

输入

2
1 4

输出

5

输入

12
3 8 15 20 7 14 9 6 11 13 5 10

输出

255

输入

7
14 14 2 13 56 2 37

输出

2354
说明

样例 1 说明

如果大会选在 P=2,第一只小羊消耗 (1-2)^2=1,第二只小羊消耗 (4-2)^2=4,总体为 5。这是最优结果。

数据范围

对于 100\% 的数据,满足 1 \leq N \leq 1001 \leq X_i \leq 100

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 3 枚
难度 基础


上一题 下一题