小慕所在的新城区学生数量激增,为了解决上学问题,他计划在一条直线上新建一所学校。考虑到学生上下学的安全,需要让所有学生家到学校的总距离尽可能短。假设学校和所有学生家都位于同一条直线上,请问学校应该建在什么位置,才能使得到各个学生家的距离之和最小?
提示:带虚线的词点一下有通俗解释。
输入描述
第一行: 整数 n 取值范围 [1, 1000],表示有n户家庭。 第二行: 一组整数 m 取值范围 [0, 10000] ,表示每户家庭的位置,所有家庭的位置都不相同。
输出描述
一个整数,确定的学校的位置。如果有多个位置,则输出最小的。
示例
示例 1
输入
5 0 20 40 10 30
输出
20
说明:20到各个家庭的距离分别为20 0 20 10 10,总和为60,最小
示例 2
输入
1 20
输出
20
说明:只有一组数据,20到20距离最小,为0
示例 3
输入
2 0 20
输出
0
说明:有多个地方可选,但是0数值最小
时间限制 1000 ms · 内存限制 128 MB