Description

Farmer John plans to open a new college for his cows!

There are $N(1 \le N \le 10^5)$ cows that might enroll. Each cow is willing to pay at most $c_i$ in tuition $(1 \le c_i \le 10^6)$. Farmer John can set a single tuition that all cows must pay to enroll. If this tuition is greater than a cow’s maximum willingness to pay, then that cow will not enroll. Farmer John wants to earn as much money as possible so he can pay his instructors well. Compute how much money he can earn and the tuition he should charge to achieve that.

Input Format

The first line contains $N$.

The second line contains $N$ integers $c_1,c_2, \cdots,c_N$, where $c_i$ is the maximum tuition cow $i$ is willing to pay.

Output Format

Output the maximum amount Farmer John can earn and the tuition he should charge in the optimal case. If there are multiple answers, output the one with the smallest tuition.

Note that the integers involved may require 64-bit integer types (e.g., long in Java, long long in C/C++).

4
1 6 4 6

12 4

Hint

Sample 1 Explanation

If Farmer John charges $4$, then $3$ cows will enroll, earning him $3 \times 4=12$.

Testpoint Properties

• Testpoints $2-4$ satisfy $c_i \le 1000$.
• Testpoints $5-8$ satisfy $N \le 5000$.
• Testpoints $9-12$ have no additional constraints.

Translated by ChatGPT 5