생산 라인의 공통 눈금

문제

한 공장의 생산 라인에서는 긴 재료 위에 여러 장치가 가공 표시를 남긴다. 점검 담당자는 같은 기준점에서 각 표시까지의 거리를 정수로 측정했다. 측정값은 장치가 보고한 순서대로 저장되므로 크기순으로 정렬되어 있지 않을 수 있다. 여러 장치가 같은 위치를 보고할 수도 있으며, 이때 같은 측정값이 여러 번 주어진다. 담당자는 표시들의 간격을 살펴보기 위해 일정한 간격의 눈금자를 설정하려 한다. 눈금 간격 D는 양의 정수다. 눈금자는 기준점에서 오른쪽으로 R만큼 이동하여 설치할 수 있으며, 이동량 R은 0 이상 D 미만인 정수여야 한다. 설치한 눈금자의 눈금은 R, R+D, R+2D와 같이 오른쪽으로 무한히 이어진다. 모든 거리는 같은 단위를 사용한다. 올바른 설정은 보고된 모든 표시가 눈금 중 하나에 정확히 놓이는 설정이다. 눈금 사이에 보고되지 않은 위치가 있거나, 여러 표시가 하나의 눈금에 겹치는 것은 허용한다. 반면 표시가 눈금과 눈금 사이에 놓이는 설정은 사용할 수 없다. 즉 모든 측정값을 D로 나눈 나머지가 동일해야 하며, 그 공통 나머지를 R로 선택한다. 눈금 간격이 지나치게 작으면 불필요한 눈금이 많아지므로, 담당자는 올바른 설정 중에서 D가 가장 큰 것을 원한다. 이동량 자체를 최소화할 필요는 없다. 최대 간격이 정해지면 조건에 맞는 이동량은 공통 나머지로 정해지므로 출력할 필요가 없다. 측정값이 두 종류 이상이면 가능한 간격 중 최댓값이 존재한다. 모든 측정값이 같을 때는 상황이 다르다. 어떤 양의 정수 D를 선택해도 그 측정값의 나머지를 이동량으로 사용하면 올바르게 설치할 수 있으므로 간격의 최댓값이 없다. 이 경우에는 특별히 -1을 출력한다. 주어진 측정값으로 설정할 수 있는 최대 눈금 간격을 구하는 프로그램을 작성한다.

입력

첫째 줄에 측정값의 개수 N이 주어진다. N은 2 ≤ N ≤ 30,000인 정수다.
둘째 줄에 측정값 A_1, A_2, …, A_N이 공백으로 주어진다. 각 A_i는 0 ≤ A_i ≤ 1,000,000,000인 정수다. 값의 중복을 허용하며 입력 순서는 임의다.

출력

가능한 눈금 간격 D의 최댓값을 정수 하나로 출력한다. 최댓값이 존재하지 않으면 -1을 출력한다.

5
29 11 47 29 65

18

4
23 23 23 23

-1

4
0 14 25 14

1

출처: Devin.KR 자체 제작