회의실 레일의 공통 간격

문제

회의실 벽에는 안내판을 고정하는 긴 레일이 설치되어 있다. 레일 위의 위치는 왼쪽 끝을 기준으로 한 정수 좌표로 나타낸다. 시설 담당자는 이미 설치된 안내판 N개의 위치를 조사했다. 안내판의 위치는 모두 다르지만, 조사한 순서대로 기록되어 있으므로 입력에 나타나는 좌표가 정렬되어 있다는 보장은 없다. 담당자는 기존 안내판을 옮기지 않고 레일에 새로운 고정점을 표시하려 한다. 먼저 기존 안내판 중 가장 왼쪽에 있는 것의 좌표를 L, 가장 오른쪽에 있는 것의 좌표를 R이라고 한다. 양의 정수 간격 d를 하나 정하면 L, L+d, L+2d와 같이 일정한 간격으로 고정점을 표시한다. R도 반드시 고정점이어야 하며, L보다 작거나 R보다 큰 위치에는 고정점을 표시하지 않는다. 기존 안내판이 있는 모든 위치 역시 고정점과 정확히 일치해야 한다. 고정점이 지나치게 많으면 레일의 눈금을 읽기 어려워지므로, 담당자는 위 조건을 만족하는 d 중 가장 큰 값을 선택한다. d를 선택한 뒤에는 기존 안내판이 없는 고정점에만 새 표시를 추가한다. 이미 안내판이 있는 고정점은 새 표시의 개수에 포함하지 않으며, L과 R에는 기존 안내판이 있으므로 이 두 위치에도 표시를 추가하지 않는다. 예를 들어 기존 좌표가 4, 10, 16이면 간격 6을 사용할 수 있고 새 표시는 필요하지 않다. 반면 기존 좌표가 4, 10, 19이면 모든 안내판을 포함하도록 더 촘촘한 간격을 사용해야 한다. 조사 기록이 주어질 때 선택할 간격과 새로 추가할 표시의 개수를 구한다. N은 항상 2 이상이므로 서로 다른 양 끝점이 존재하고, 간격 1은 언제나 사용할 수 있다. 따라서 조건을 만족하는 간격이 없는 경우는 발생하지 않는다.

입력

첫째 줄에 안내판의 개수 N이 주어진다. N은 2 이상 40,000 이하의 정수다.
둘째 줄에 안내판의 좌표 N개가 공백으로 구분되어 주어진다. 각 좌표는 0 이상 1,000,000 이하의 정수이며, 모든 좌표는 서로 다르다. 좌표의 입력 순서는 임의다.

출력

가장 큰 간격 d와 새로 추가할 표시의 개수를 순서대로 한 줄에 공백으로 구분하여 출력한다. 새 표시가 필요하지 않으면 두 번째 값으로 0을 출력한다.

3
19 4 10

3 3

4
23 5 17 11

6 0

2
0 1

1 0

출처: Devin.KR 자체 제작