우편 보관함의 공통 눈금

문제

우체국은 긴 벽을 따라 임시 우편 보관함을 설치했다. 벽에는 왼쪽 기준점으로부터의 거리를 나타내는 정수 좌표가 있으며, 각 보관함의 설치 위치도 이 좌표로 기록되어 있다. 담당자는 보관함을 옮기지 않고, 현재 위치들을 모두 표시할 수 있는 일정한 간격의 눈금자를 만들려고 한다. 여러 기록이 같은 위치를 가리킬 수도 있다. 이 경우에도 입력 기록을 삭제할 필요는 없다. 눈금자는 정수 간격 d와 시작 좌표 r로 정한다. d는 양의 정수이고, r은 0 이상 d 미만인 정수다. 이 눈금자가 나타내는 좌표는 r, r+d, r+2d와 같이 r에 d의 음이 아닌 정수배를 더한 값들이다. 모든 보관함 좌표가 이 중 하나와 정확히 일치하면 해당 눈금자는 설치 기록을 표시할 수 있다. 눈금이 실제 보관함이 없는 좌표를 가리키는 것은 허용한다. 또한 기준점인 좌표 0에 반드시 눈금이 있어야 하는 것은 아니다. 눈금 간격이 클수록 벽에 그려야 할 표시가 줄어들기 때문에, 담당자는 가능한 d 중 가장 큰 값을 원한다. 예를 들어 두 위치의 차이가 d의 정수배가 아니면 두 위치를 같은 눈금자로 표시할 수 없다. 반면 시작 좌표 r은 기록에 맞게 자유롭게 정할 수 있으므로 가장 작은 보관함 좌표를 0으로 간주해서는 안 된다. 가능한 간격에 최댓값이 없는 경우도 있다. 모든 기록이 같은 위치라면 어떤 양의 정수 간격을 택하더라도 그 위치를 포함하는 시작 좌표를 정할 수 있다. 기록이 하나뿐인 경우도 여기에 해당한다. 주어진 모든 위치를 표시하는 가장 큰 정수 간격을 구하고, 간격을 제한 없이 크게 정할 수 있으면 정해진 표시값을 출력한다. 눈금자의 시작 좌표나 실제 눈금 목록은 출력하지 않는다.

입력

첫째 줄에 보관함 위치 기록 수 N이 주어진다. 1≤N≤30,000이다.
둘째 줄에 좌표 x1, x2, …, xN이 공백으로 주어진다. 각 좌표는 0 이상 1,000,000,000 이하의 정수다. 좌표는 정렬되어 있지 않을 수 있으며 같은 좌표가 여러 번 주어질 수 있다.

출력

모든 위치를 표시할 수 있는 가장 큰 양의 정수 간격 d를 출력한다. 가능한 간격에 최댓값이 없으면 -1을 출력한다. 시작 좌표가 여러 개 가능하더라도 간격만 출력한다.

5
14 38 26 62 38

12

3
7 7 7

-1

4
10 19 25 32

1

출처: Devin.KR 자체 제작