코스마다 맞는 급수 간격

문제

마라톤 대회 운영팀은 길이가 서로 다른 N개의 직선 코스에 급수 지점을 설치하려고 한다. i번 코스의 길이는 A_i미터이며, 모든 코스는 출발점의 위치를 0미터로 두고 거리를 잰다. 코스가 서로 다른 장소에 있어도 급수 지점을 설치하는 간격은 하나로 통일하려고 한다. 운영팀이 간격 D미터를 선택하면 각 코스의 0미터 지점부터 D미터마다 급수 지점을 설치한다. 따라서 설치 위치는 0, D, 2D, 3D, …미터 순서가 된다. 각 코스의 도착점에도 반드시 급수 지점이 있어야 하며, 마지막 두 급수 지점 사이의 간격만 줄이는 등의 예외는 허용하지 않는다. 즉, 출발점부터 도착점까지 모든 이웃한 급수 지점 사이의 거리가 정확히 D미터여야 한다. 간격 D는 정수여야 하며, 운영팀이 정한 하한 L 이상 상한 R 이하여야 한다. L과 R도 정수이고 양 끝값을 모두 허용한다. 모든 코스에 같은 D를 사용해야 하므로, 어떤 코스에는 적용할 수 있지만 다른 코스에는 적용할 수 없는 간격은 후보에서 제외한다. 코스마다 설치되는 급수 지점의 개수는 서로 달라도 된다. 운영팀은 설치 인력 배치안을 비교하기 위해 조건을 만족하는 서로 다른 간격의 개수를 알고 싶어 한다. 또한 가능한 간격 중 가장 큰 값으로 설치하는 안도 함께 검토하려고 한다. 간격 하나가 모든 코스에 적용되면 하나의 후보로 세며, 코스의 수나 설치되는 급수 지점의 수만큼 중복해서 세지 않는다. 주어진 코스 길이와 허용 범위를 이용하여 가능한 간격의 개수와 그중 가장 큰 값을 구하는 프로그램을 작성한다. 허용 범위에 조건을 만족하는 간격이 하나도 없을 수도 있으며, 이 경우에는 정해진 형식에 따라 후보가 없음을 출력한다.

입력

첫째 줄에 세 정수 N, L, R이 공백으로 구분되어 주어진다.
둘째 줄에 N개의 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다.
1 ≤ N ≤ 20,000, 1 ≤ L ≤ R ≤ 1,000,000,000이다.
모든 i에 대해 1 ≤ A_i ≤ 1,000,000,000이다.

출력

첫째 줄에 가능한 간격의 개수와 그중 가장 큰 간격을 공백으로 구분하여 출력한다. 가능한 간격이 없으면 0 -1을 출력한다.

3 4 15
60 84 108

3 12

2 7 11
18 30

0 -1

1 6 6
36

1 6

출처: Devin.KR 자체 제작