같은 구성의 배달 꾸러미

문제

배달 앱에서 여러 종류의 간식을 모아 공동 주문용 꾸러미를 만들려고 한다. 준비된 간식은 N종류이며, i번 종류의 간식은 A_i개 있다. 서로 다른 종류의 간식은 겉모양이나 가격이 같더라도 다른 종류로 취급한다. 모든 간식은 개별 포장이 끝난 상태이므로 하나를 쪼개서 여러 꾸러미에 나누어 담을 수 없다. 운영 담당자는 준비된 간식을 하나도 남기지 않고 K개의 꾸러미에 나누어 담으려고 한다. K는 1 이상의 정수이며, 모든 꾸러미의 구성은 정확히 같아야 한다. 여기서 구성이 같다는 것은 각 종류에 대해 그 종류의 간식 개수가 모든 꾸러미에서 같다는 뜻이다. 꾸러미에 들어 있는 전체 간식 수만 같고 종류별 개수가 다른 경우는 허용하지 않는다. 예를 들어 어떤 종류의 간식이 여섯 개 있다면 꾸러미 세 개에 두 개씩 나누어 담을 수 있다. 하지만 다른 종류의 간식 수가 세 꾸러미에 똑같이 나누어지지 않는다면, 전체 주문을 세 꾸러미로 만드는 것은 불가능하다. 각 종류에 대해 같은 수의 꾸러미를 사용할 수 있어야 하며, 일부 종류만 별도의 꾸러미로 보내는 방법도 허용하지 않는다. 앱은 공동 주문을 나누어 받을 수 있는 사람을 최대한 늘리기 위해 가능한 K 중 가장 큰 값을 선택한다. 꾸러미의 용량 제한은 없고, 간식 종류에 따라 별도의 포장 조건도 없다. 각 A_i는 양수이므로 선택한 모든 꾸러미에는 모든 종류의 간식이 적어도 하나씩 들어가야 한다. 만들 수 있는 꾸러미 수의 최댓값과, 그때 꾸러미 하나에 들어가는 간식의 전체 개수를 구하는 프로그램을 작성한다. 꾸러미 하나를 만드는 방법은 항상 가능하므로 불가능한 경우를 위한 별도 출력은 없다.

입력

첫째 줄에 간식 종류 수 N이 주어진다.
둘째 줄에 N개의 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다.
1 ≤ N ≤ 60,000이며, 모든 i에 대해 1 ≤ A_i ≤ 99,999이다.

출력

첫째 줄에 만들 수 있는 꾸러미 수의 최댓값 K와, 그때 꾸러미 하나에 들어가는 간식의 전체 개수를 공백으로 구분하여 출력한다.

3
18 30 42

6 15

4
8 15 21 10

1 54

1
99

99 1

출처: Devin.KR 자체 제작