Nông dân John đang dự định mở một trường đại học mới cho các chú bò!

Có tổng cộng \(N (1 \le N \le 10^5)\) chú bò có thể dự định nhập học vào trường này. Mỗi chú bò sẵn sàng trả một mức học phí tối đa là \(c_i (1 \le c_i \le 10^6)\). Nông dân John có thể điều chỉnh học phí sao cho mọi chú bò phải trả để nhập học. Nếu mức học phí vượt mức tối đa mà một chú bò sẵn sàng chi, chú bò này sẽ không nhập học. Nông dân John muốn kiếm thật nhiều tiền để có thể trả lương cho các giảng viên một cách công bằng nhất. Hãy cho biết lượng tiền mà bác John có thể kiếm được, và lượng học phí mà bác John cần điều chỉnh.

Input

• Dòng đầu tiên là số \(N\).
• Dòng thứ hai là \(N\) số \(c_1, c_2, \dots, c_N\), trong đó \(c_i\).

Output

• Lượng tiền tối đa mà bác John có thể kiếm được, và lượng học phí mà bác John cần điều chỉnh.

Scoring

• Subtask \(1\): \(c_i \le 1000\).
• Subtask \(2\): \(N \le 5000\).
• Subtask \(3\): Không có thêm ràng buộc.

4
1 6 4 6

12 4