Farmer John plant, eine neue Universität für Kühe zu eröffnen!
Es gibt $N$ Kühe ($1 \le N \le 10^5$), die diese Universität möglicherweise besuchen könnten. Jede Kuh ist bereit, eine Studiengebühr von höchstens $c_i$ zu zahlen ($1 \le c_i \le 10^6$). Farmer John kann die Studiengebühr festlegen, die alle Kühe zur Einschreibung zahlen müssen. Übersteigt diese Gebühr den Höchstbetrag, den eine Kuh zu zahlen bereit ist, besucht sie die Universität nicht. Farmer John möchte möglichst viel Geld verdienen, damit er seinen Lehrkräften einen fairen Lohn zahlen kann. Bestimme, wie viel Geld er verdienen kann und welche Studiengebühr er verlangen sollte.
Eingabe
Die erste Zeile enthält $N$. Die zweite Zeile enthält $N$ ganze Zahlen $c_1, c_2, \dots, c_N$, wobei $c_i$ die maximale Studiengebühr ist, die Kuh $i$ zu zahlen bereit ist.
Ausgabe
Gib den maximalen Geldbetrag aus, den Farmer John verdienen kann, sowie die optimale Studiengebühr, die er verlangen sollte. Gibt es mehrere Lösungen, gib die Lösung mit der kleinsten optimalen Studiengebühr aus.
Beachte, dass die großen Ganzzahlwerte in dieser Aufgabe die Verwendung von 64-Bit-Ganzzahltypen erfordern können (zum Beispiel "long" in Java oder "long long" in C/C++).
Beispiele
Eingabe 1
4 1 6 4 6
Ausgabe 1
12 4
Hinweis
Wenn Farmer John $4$ verlangt, besuchen $3$ Kühe die Universität, wodurch er $3 \cdot 4 = 12$ verdient.
Teilaufgaben
- Die Testfälle 2 bis 4 erfüllen $c_i \le 1{,}000$.
- Die Testfälle 5 bis 8 erfüllen $N \le 5{,}000$.
- Für die Testfälle 9 bis 12 gelten keine zusätzlichen Beschränkungen.
Aufgabenautor: Freddie Tang