점검 기록의 공통 주기

문제

사내 IT 지원팀은 여러 장비의 자동 점검 기록을 하나의 시간표로 정리하려 한다. 각 기록에는 기준 시각으로부터 몇 분이 지났는지를 나타내는 정수가 적혀 있다. 기록은 시간순으로 정렬되어 있지 않을 수 있으며, 서로 다른 장비가 같은 시각에 점검되었다면 같은 값이 여러 번 나타날 수도 있다. 지원팀은 기록이 어느 장비에서 나왔는지와 관계없이 기록된 시각만 사용한다. 새 시간표는 양의 정수 D와 정수 R로 정한다. D는 점검 주기이고 R은 기준 시각에서 첫 점검까지의 대기 시간이다. R은 0 이상 D 미만이어야 한다. 이 시간표에서 점검할 수 있는 시각은 R, R+D, R+2D, ...이다. 주어진 모든 기록의 시각이 이 시간표에 포함되어야 한다. 시간표에 포함된 시각 중 실제 기록이 없는 시각이 있어도 괜찮으며, 같은 시각의 기록이 여러 개 있어도 시간표에서 그 시각을 여러 번 만들 필요는 없다. 지원팀은 가능한 시간표 중 D가 가장 큰 것을 찾으려 한다. 가능한 D가 아무리 커도 그보다 더 큰 D를 선택할 수 있다면 최대 주기가 존재하지 않는 것으로 처리한다. 예를 들어 기록된 시각이 모두 같으면 충분히 큰 D를 계속 선택할 수 있으므로 최대 주기가 존재하지 않는다. 이 경우에는 별도의 값을 출력해야 한다. 기록된 시각이 서로 다른 경우에는 그 시각들이 동일한 시간표에 속하도록 주기를 정해야 한다. 기록의 입력 순서를 바꾸거나 같은 시각의 중복 기록을 제거하는 것은 가능한 시간표에 영향을 주지 않는다. 최대 주기 D가 정해지면 0 이상 D 미만인 R은 하나로 결정되므로 추가 동점 규칙은 없다. 모든 기록을 포함하는 최대 주기와 대기 시간을 구하는 프로그램을 작성한다. 최대 주기가 존재하지 않는 경우와, 주기가 1이라서 매분 점검하는 경우는 서로 구분하여 출력한다.

입력

첫째 줄에 기록의 수를 나타내는 정수 N이 주어진다. (1 ≤ N ≤ 30,000)
둘째 줄에 각 기록의 시각을 나타내는 정수 T_1, T_2, ..., T_N이 공백으로 구분되어 주어진다. (0 ≤ T_i ≤ 1,000,000,000)
시각은 정렬되어 있지 않을 수 있으며 중복을 허용한다.

출력

최대 주기가 존재하면 D와 R을 공백으로 구분하여 한 줄에 출력한다. 가능한 D에 유한한 최댓값이 없으면 -1만 출력한다.

4
38 14 50 26

12 2

3
7 7 7

-1

4
8 20 15 8

1 0

출처: Devin.KR 자체 제작