传统题 1000ms 256MiB

D. 中位训练

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

一次训练记录了 nn 名同学的完成时间。为了选出最接近整体水平的参考值,先将所有完成时间按非递减顺序排列,记排序后的数组为 bb。

由于 nn 一定是奇数,定义中位数为:

med=b(n+1)/2,\mathrm{med}=b_{(n+1)/2},

其中下标从 11 开始。

请输出中位数,以及所有完成时间与中位数的绝对差之和:

∑i=1n∣ai−med∣.\sum_{i=1}^{n}|a_i-\mathrm{med}|.

输入

第一行输入一个奇数 nn。

第二行输入 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

输出

输出一行两个整数,依次表示中位数和绝对差之和。

数据范围

  • 1≤n≤2000011\le n\le 200001,且 nn 为奇数;
  • ∣ai∣≤109|a_i|\le 10^9;
  • 绝对差之和可以用有符号 64 位整数表示。

样例

5
7 1 5 3 9
5 12

排序后为 1,3,5,7,91,3,5,7,9,因此中位数为 55,绝对差之和为 4+2+0+2+4=124+2+0+2+4=12。

说明

输入中的数据不保证有序,且可能包含重复值和负数。