항공권 정산 묶음의 크기

문제

한 항공권 판매 서비스가 여러 판매 창구의 정산 자료를 한꺼번에 보관하려 한다. 각 창구는 그날 발권한 항공권마다 정산 항목을 하나씩 만들었으며, 창구별 항목 수가 양의 정수로 주어진다. 정산 항목은 내용과 관계없이 하나를 한 단위로 센다. 서비스는 파일 형식을 통일하기 위해 모든 창구에 같은 묶음 크기를 적용하려 한다. 묶음 크기 d를 선택하면 각 창구의 항목을 정확히 d개씩 묶어 저장한다. 한 묶음에는 반드시 같은 창구에서 나온 항목만 들어가야 한다. 서로 다른 창구의 남은 항목을 합쳐서 묶을 수 없으며, 항목을 버리거나 복사하거나 다음 날로 넘길 수도 없다. 따라서 모든 창구가 자신의 항목을 하나도 남기지 않고 묶을 수 있어야 그 크기를 사용할 수 있다. 각 창구에서 만들어지는 묶음 수는 서로 달라도 된다. 항목 하나만 담는 묶음은 보관 파일 수를 줄이는 데 도움이 되지 않으므로 허용하지 않는다. 사용할 수 있는 묶음 크기 d는 2 이상의 정수다. 예를 들어 두 창구의 항목 수가 각각 18개와 30개라면 크기 3은 사용할 수 있지만, 크기 5는 첫 번째 창구에서 항목이 남으므로 사용할 수 없다. 어떤 창구의 항목 수보다 큰 크기를 선택해 그 창구에 묶음을 하나도 만들지 않는 것도 허용하지 않는다. 모든 항목은 반드시 묶음에 포함되어야 한다. 운영 담당자는 가능한 크기를 모두 검토한 뒤, 사용할 수 있는 서로 다른 묶음 크기의 개수와 그중 가장 큰 크기를 보고하려 한다. 크기가 같다면 각 창구에서 항목을 나누는 순서나 묶음을 저장하는 순서가 달라도 같은 선택으로 센다. 주어진 모든 창구에 공통으로 적용할 수 있는 묶음 크기를 조사하는 프로그램을 작성한다. 사용할 수 있는 크기가 하나도 없다면 개수는 0, 가장 큰 크기는 -1로 보고한다.

입력

첫째 줄에 판매 창구 수 N이 주어진다. N은 1 이상 30,000 이하의 정수다.
둘째 줄에 각 창구의 정산 항목 수 A₁, A₂, …, Aₙ이 공백으로 구분되어 주어진다. 모든 Aᵢ는 1 이상 1,000,000,000 이하의 정수다.

출력

사용할 수 있는 서로 다른 묶음 크기의 개수와 그중 가장 큰 크기를 공백으로 구분하여 한 줄에 출력한다. 사용할 수 있는 크기가 없으면 0 -1을 출력한다.

3
24 60 84

5 12

3
14 25 39

0 -1

1
49

2 49

출처: Devin.KR 자체 제작