2043 - 最佳位置

题目描述

贝壳街上有很多家住户,小丁准备在该条街上开一家商店,请问,他的商店开在哪里,可以使得所有住户到商店的距离的总和是最小的

本题中,假设该条街是一条笔直的街道,街道的起始位置标记为 0 ,已知每个住户离起点的距离。

本题要求的位置可以是街道中的任何一个位置,也可以和住户的位置是重叠的,如果有多个位置到所有住户的距离总和都是最小的,请输出可选位置的最大值

输入

输入的第一行是一个整数 T ,表示有 T 组测试数据。

每组测试数据第一行是一个整数 N1 \le N \le 1000 )表示在贝壳街上共有 N 个住户。

接下来 N 行,每行一个整数 a_i0 \le a_i \le 30000 )表示每个住户住所的位置,所有住户住所的位置均不相同。

输出

对于每组输入,输出一行,包含两个整数,分别是你确定的商店位置,以及商店到所有住户住所的距离之和。

样例

输入

2
5
0
20
40
10
30
1
20

输出

20 60
20 0
来源

贪心

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


上一题 下一题