T3 火锅的定价

时间：1s

空间：256M

题目描述

火锅广场的老板现在想要给他的火锅重新定价，他调查了 N 位顾客的期望价格，每位顾客最多愿意支付 $w_i$ 的餐费，如果老板设定的价格大于这个期望价格，这位顾客就不会来吃火锅了。老板想知道，他如何定价能够让他的利益最大化。请给出定价，以及平均意义上能从每 N 位市民收取到的餐费总和。(这里，我们认为这 N 位顾客就代表了一种平均意义) 若有多个合法解，保留定价最低的价，以便让更多的人吃到火锅。

输入格式

输入包含两行。

第一行为一个整数 N ,代表调查的顾客数量。

第二行包含 N 个整数 $w_i$ ,代表第 i 位被调查的顾客最多愿意支付多少餐费。

输出格式

输出两个整数，代表每 N 位市民可以给老板带来的收入和最终的定价。

样例输入输出

4
1 6 4 6

12 4

说明/提示

样例提示

定价 4 元，将有 3 位顾客愿意买单，所以最终价格是 4 元， 共收入 $4\times3=12$ 元。

数据范围

对于 $30\%$ 的数据，有 $1\le w_i \le 10^3$,

对于 $60\%$ 的数据，有 $1\le n \le 10^4$,

对于 $100\%$ 的数据，有 $1\le n \le 10^5$，$1\le w_i \le 10^9$。