You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

光头强在四川开了一个火锅店,现在想要给他的火锅重新定价，他调查了 $N$ 位顾客的期望价格，每位顾客最多愿意支付 $w_i$ 的餐费，如果光头强设定的价格大于这个期望价格，这位顾客就不会来吃火锅了。光头强想知道，他如何定价能够让他的利益最大化。

请给出定价，以及平均意义上能从每 $N$ 位市民收取到的餐费总和。(这里，我们认为这 $N$ 位顾客就代表了一种平均意义) 若有多个合法解，保留定价最低的价，以便让更多的人吃到火锅。

输入格式

输入包含两行。

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

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

输出格式

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

4
1 6 4 6

12 4

说明/提示

样例提示

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

数据范围

总收益可能会超过int范围,

对于 $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$。对于 $100\%$ 的数据，有 $1\le n \le 10^5$。