예약 알림의 공통 간격

문제

한 병원은 진료 예약 시각에 맞추어 자동 알림을 보내는 장치를 시험하고 있다. 예약 시각은 시험을 시작한 기준 시각으로부터 몇 분 뒤인지를 나타내는 정수로 기록한다. 이번 시험에 사용할 예약은 N개이며, 서로 같은 시각의 예약은 없다. 입력되는 예약 목록은 시각순으로 정렬되어 있지 않을 수도 있다. 알림 장치는 처음 설정한 시각부터 일정한 간격으로 계속 작동한다. 관리인은 예약 시각 중 가장 이른 시각을 첫 작동 시각으로 설정한다. 그 뒤 장치는 정확히 d분마다 한 번씩 작동한다. d는 2 이상인 정수여야 한다. 예를 들어 첫 작동 시각이 7이고 간격이 4라면 장치는 7, 11, 15, 19와 같은 시각에 작동한다. 시험을 통과하려면 모든 예약 시각에 장치가 작동해야 한다. 다만 예약이 없는 시각에 추가로 작동하는 것은 허용한다. 한 번의 작동으로 해당 시각의 알림을 처리할 수 있으며, 예약 순서나 예약 번호는 설정 가능 여부에 영향을 주지 않는다. 장치를 켜 두는 총시간에는 별도의 제한이 없으므로 마지막 예약 이후의 작동도 고려하지 않는다. 관리인은 불필요한 작동을 줄이기 위해 시험을 통과하는 간격 중 가장 큰 값을 선택하려 한다. 간격은 반드시 정수 분 단위여야 하며, 소수 간격이나 예약마다 다른 간격을 사용할 수 없다. 예약 시각이 적어도 두 개이고 모두 다르므로 가능한 간격이 있다면 그 최댓값은 유한하다. 모든 예약에 맞추려면 1분 간격으로 작동해야 하는 경우에는 허용되는 설정이 없다고 본다. 주어진 예약 목록으로 선택할 수 있는 가장 큰 간격을 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N이 주어진다. 둘째 줄에 예약 시각 T1, T2, …, TN이 공백으로 구분되어 주어진다.
2 ≤ N ≤ 40,000이다. 모든 Ti는 0 이상 1,000,000 이하의 정수이며, 서로 다르다.

출력

모든 예약 시각에 작동할 수 있는 가장 큰 정수 간격 d를 출력한다. 2 이상의 가능한 간격이 없으면 0을 출력한다.

4
38 8 26 20

6

3
2 9 13

0

2
100 0

100

출처: Devin.KR 자체 제작