Farmer John đang dự định mở một trường đại học mới cho bò!

Có $N$ cô bò ($1 \le N \le 10^5$) có thể theo học trường đại học này. Mỗi cô bò sẵn sàng trả học phí tối đa là $c_i$ ($1 \le c_i \le 10^6$). Farmer John có thể đặt mức học phí mà tất cả các cô bò phải trả để nhập học. Nếu mức học phí này lớn hơn mức tối đa mà một cô bò sẵn sàng trả, cô bò đó sẽ không theo học. Farmer John muốn kiếm được nhiều tiền nhất có thể để trả lương công bằng cho các giảng viên. Hãy xác định số tiền ông có thể kiếm được và mức học phí ông nên thu.

Dữ liệu vào

Dòng đầu tiên chứa $N$. Dòng thứ hai chứa $N$ số nguyên $c_1, c_2, \dots, c_N$, trong đó $c_i$ là mức học phí tối đa mà cô bò $i$ sẵn sàng trả.

Dữ liệu ra

Hãy in ra số tiền lớn nhất Farmer John có thể kiếm được và mức học phí tối ưu ông nên thu. Nếu có nhiều lời giải, in lời giải có mức học phí tối ưu nhỏ nhất.

Lưu ý rằng các số nguyên trong bài toán này có thể rất lớn nên có thể cần dùng kiểu số nguyên 64 bit (ví dụ, "long" trong Java hoặc "long long" trong C/C++).

Ví dụ

Dữ liệu vào 1

4
1 6 4 6

Dữ liệu ra 1

12 4

Ghi chú

Nếu Farmer John thu $4$, sẽ có $3$ cô bò theo học, cho phép ông kiếm được $3 \cdot 4 = 12$.

Nhiệm vụ con

• Các bộ kiểm thử từ 2 đến 4 thỏa mãn $c_i \le 1{,}000$.
• Các bộ kiểm thử từ 5 đến 8 thỏa mãn $N \le 5{,}000$.
• Các bộ kiểm thử từ 9 đến 12 không có ràng buộc bổ sung.

Tác giả bài toán: Freddie Tang