창구의 동전 봉투 분류

문제

한 은행 창구에 동전이 들어 있는 봉투 N개가 도착했다. 각 봉투에는 같은 종류의 동전만 들어 있으며, 봉투 겉면에는 동전의 개수가 적혀 있다. 창구 직원은 동전의 금액 대신 개수만 보고 봉투를 분류한다. 서로 다른 봉투의 동전을 섞는 일은 없으며, 동전 하나를 더 작은 단위로 나눌 수도 없다. 직원은 동전이 여러 개 들어 있는 봉투를 더 작은 봉투들로 똑같이 나눌 수 있는지 확인한다. 나누기가 가능하려면 새 봉투를 두 개 이상 만들어야 하고, 새 봉투마다 동전이 두 개 이상 들어 있어야 한다. 모든 새 봉투의 동전 개수는 같아야 하며, 원래 봉투에 있던 동전을 하나도 남기지 않고 전부 사용해야 한다. 새 봉투의 개수나 새 봉투 하나에 넣는 동전 개수에는 이 조건 외의 제한이 없다. 동전이 두 개 이상 들어 있지만 위 규칙으로는 나눌 수 없는 봉투를 개별 확인 대상으로 지정한다. 동전이 한 개뿐인 봉투는 별도의 단일 동전 보관함으로 보내므로 개별 확인 대상에 포함하지 않는다. 봉투의 크기나 접수된 순서도 분류에 영향을 주지 않는다. 동전 개수가 같은 봉투가 여러 개 도착했다면 각각 실제로 존재하는 별개의 봉투로 취급한다. 예를 들어 동전 수가 두 정수의 곱으로 표현되고 두 정수가 모두 2 이상이면, 한 정수를 새 봉투의 개수로 정하고 다른 정수를 봉투마다 넣을 동전 개수로 정할 수 있다. 반면 그러한 두 정수를 찾을 수 없고 동전이 두 개 이상이라면 그 봉투는 개별 확인 대상이 된다. 어떤 나누기 방법을 선택했는지 출력할 필요는 없다. 직원이 준비해야 할 개별 확인 대상 봉투의 개수와, 그 대상 봉투들에 적힌 동전 개수 중 최댓값을 구한다. 같은 최댓값을 가진 대상 봉투가 여러 개여도 최댓값은 한 번만 출력한다. 개별 확인 대상이 하나도 없으면 대상 개수와 최댓값을 모두 0으로 출력한다.

입력

첫째 줄에 봉투 수를 나타내는 정수 N이 주어진다. 1≤N≤100,000이다.
둘째 줄에 각 봉투의 동전 개수를 나타내는 정수 A₁, A₂, …, Aₙ이 공백으로 구분되어 주어진다. 1≤Aᵢ≤100,000이다.

출력

개별 확인 대상 봉투의 개수와 대상 봉투의 동전 개수 중 최댓값을 공백으로 구분하여 한 줄에 출력한다. 대상이 없으면 0 0을 출력한다.

7
1 2 4 7 9 11 7

4 11

5
1 4 6 8 100

0 0

3
2 2 2

3 2

출처: Devin.KR 자체 제작