Bác Nông dân John sắp mở một trường Đại học mới cho Bò!

Có \(N\) con bò có khả năng dự đại học. Mỗi con bò có khả năng chi trả mức học phí cao nhất là \(c_i\) đồng. Bác John có thể chốt mức học phí mà tất cả loài bò đều phải đóng. Nếu mức học phí này lớn hơn khả năng chỉ trả cao nhất của một con bò nào đó, thì con bò đó sẽ không đi học đại học nữa. Bác John muốn kiếm được nhiều tiền nhất có thể để bác có thể trả các giảng viên một mức lương xứng đáng. Hãy xác định số tiền mà bác có thể kiếm được, và mức học phí mà các con bò phải đóng.

Dữ liệu đầu vào

• Dòng đầu tiên chứa số \(N\) \((1 \leq N \leq 10^5)\)
• Dòng thứ hai chứa \(N\) số nguyên \(c_1, c_2, \dots, c_N\) \((1 \leq c_i \leq 10^6)\); với \(c_i\) là mức học phí tối đa mà con bò thứ \(i\) có thể sẵn sàng chi trả.

Định dạng đầu ra

• In ra tổng số tiền tối đa mà bác John có thể kiếm được, và mức học phí mà bác John nên thu. Nếu có nhiều đáp án khác nhau, in ra đáp án với mức học phí thấp nhất.

Điểm số

Bài có 12 testcase

• Test 1 là test ví dụ
• Test 2 tới 4 có \(c_i \leq 1000\)
• Test 5 tới 8 có \(N \leq 5000\)
• Test 9 tới 12 không có giới hạn nào khác.

Ví dụ

4
1 6 4 6

12 4

Người ra đề: Freddie Tang