Farmer John은 소를 위한 새로운 대학을 열 계획이다!

이 대학에 다닐 가능성이 있는 소가 $N$마리 있다 ($1 \le N \le 10^5$). 각 소가 지불할 의향이 있는 등록금의 최댓값은 $c_i$이다 ($1 \le c_i \le 10^6$). Farmer John은 모든 소가 입학하기 위해 지불해야 하는 등록금을 정할 수 있다. 이 등록금이 어떤 소가 지불할 의향이 있는 최댓값보다 크면, 그 소는 대학에 다니지 않는다. Farmer John은 강사들에게 공정한 임금을 지급할 수 있도록 가능한 한 많은 돈을 벌고 싶다. 그가 벌 수 있는 돈과 책정해야 할 등록금을 구하여라.

입력

첫 번째 줄에는 $N$이 주어진다. 두 번째 줄에는 $N$개의 정수 $c_1, c_2, \dots, c_N$이 주어지며, $c_i$는 소 $i$가 지불할 의향이 있는 등록금의 최댓값이다.

출력

Farmer John이 벌 수 있는 돈의 최댓값과 책정해야 할 최적의 등록금을 출력하여라. 해가 여러 개이면 최적의 등록금이 가장 작은 해를 출력하여라.

이 문제에 등장하는 정수가 크므로 64비트 정수 자료형(예를 들어 Java의 "long", C/C++의 "long long")을 사용해야 할 수도 있음에 유의하여라.

예제

입력 1

4
1 6 4 6

출력 1

12 4

참고

Farmer John이 $4$를 받으면 소 $3$마리가 대학에 다니며, $3 \cdot 4 = 12$를 벌 수 있다.

서브태스크

• 테스트 케이스 2부터 4까지는 $c_i \le 1{,}000$을 만족한다.
• 테스트 케이스 5부터 8까지는 $N \le 5{,}000$을 만족한다.
• 테스트 케이스 9부터 12까지에는 추가 제한이 없다.

문제 작성: Freddie Tang