소 대학

Farmer John은 소를 위한 새 대학교를 열 계획이다. 등록을 고려할 수 있는 소는 $N$마리($1 \le N \le 10^5$)이다. 각 소가 낼 수 있는 최대 등록금은 $c_i$($1 \le c_i \le 10^6$)이다. Farmer John은 모든 소가 등록할 때 내야 하는 등록금을 하나 정할 수 있다. 등록금이 소가 낼 수 있는 최대 금액보다 높으면 그 소는 입학하지 않는다. Farmer John은 강사에게 공정한 임금을 주려고 가능한 한 많은 돈을 벌고자 한다. 벌 수 있는 최대 금액과 그때 받아야 할 최적의 등록금을 구하라.

첫 번째 줄에 $N$이 주어진다. 두 번째 줄에는 정수 $c_1, c_2, \dots, c_N$이 주어지며, $c_i$는 $i$번째 소가 낼 수 있는 최대 등록금이다.

Farmer John이 벌 수 있는 최대 금액과 그가 받아야 할 최적의 등록금을 출력한다. 최적의 해가 여러 개라면 최적 등록금이 가장 작은 해를 출력한다. 다루는 수가 클 수 있으므로 64비트 정수 자료형을 써야 할 수 있다.

Farmer John이 등록금을 $4$로 정하면 $3$마리의 소가 입학하므로 $3 \cdot 4 = 12$를 번다.