Farmer John 计划开办一所新的奶牛大学！

有 $N$ ($1 \le N \le 10^5$) 头奶牛可能就读这所大学。每头奶牛最多愿意支付 $c_i$ ($1 \le c_i \le 10^6$) 的学费。Farmer John 可以设定所有奶牛入学时都必须支付的学费。如果这一学费超过某头奶牛愿意支付的最大金额，这头奶牛就不会就读。Farmer John 希望尽可能多地赚钱，以便为教师支付公平的工资。请确定他最多能赚多少钱，以及应该收取多少学费。

输入格式

第一行包含 $N$。第二行包含 $N$ 个整数 $c_1, c_2, \dots, c_N$，其中 $c_i$ 是奶牛 $i$ 愿意支付的最高学费。

输出格式

请输出 Farmer John 能赚到的最大金额以及应该收取的最优学费。如果有多个方案，输出最优学费最小的方案。

注意，本题涉及的整数可能很大，因此可能需要使用 64 位整数类型（例如 Java 中的 "long"，C/C++ 中的 "long long"）。

样例

输入格式 1

4
1 6 4 6

输出格式 1

12 4

说明

如果 Farmer John 收取 $4$ 的学费，就会有 $3$ 头奶牛就读，使他赚到 $3 \cdot 4 = 12$。

子任务

• 测试点 2 到 4 满足 $c_i \le 1{,}000$。
• 测试点 5 到 8 满足 $N \le 5{,}000$。
• 测试点 9 到 12 没有额外限制。

题目作者：Freddie Tang