메신저 기록 묶음의 크기

문제

한 회사의 사내 메신저는 대화방별로 하루 동안 생성된 기록을 모아 보관한다. 기록 하나는 분리할 수 없는 저장 단위이며, 대화방마다 보관할 기록의 개수가 다를 수 있다. 저장 담당자는 기록을 일정한 개수씩 묶어 전송하려 한다. 전송 도구는 모든 대화방에서 같은 묶음 크기를 사용해야 하므로, 대화방마다 서로 다른 크기를 정할 수는 없다. 묶음 크기 K는 묶음 하나에 들어가는 기록의 개수를 뜻한다. K를 선택하면 각 대화방의 기록을 정확히 K개씩 나누어 여러 묶음으로 만든다. 마지막에 기록이 남는 불완전한 묶음은 허용하지 않는다. 다른 대화방의 기록을 가져와 부족한 자리를 채우거나, 서로 다른 대화방의 기록을 한 묶음에 넣는 것도 허용하지 않는다. 따라서 모든 대화방의 기록 개수가 각각 K로 나누어떨어져야 한다. 전송 도구가 허용하는 묶음 크기의 범위는 L 이상 R 이하이다. L과 R은 모두 양의 정수이며 양 끝값도 후보에 포함된다. 범위 안에 있는 정수 K 중에서 모든 대화방의 기록을 남김없이 묶을 수 있는 값을 유효한 묶음 크기라고 한다. 같은 K로 여러 대화방을 처리하더라도 그 K는 한 가지 크기로만 센다. 묶음의 전체 개수나 대화방을 처리하는 순서는 유효성에 영향을 주지 않는다. 대화방은 N개이며 각 대화방의 기록 개수는 양의 정수로 주어진다. 모든 대화방의 기록을 한 번에 살펴보고, 허용 범위 안에 유효한 묶음 크기가 몇 개 있는지 구한다. 그중 가장 큰 크기도 함께 구해야 한다. 유효한 크기가 여러 개이면 최댓값 하나만 두 번째 값으로 출력하므로 별도의 동점 처리는 없다. 허용 범위 안에서 조건을 만족하는 크기가 없을 수도 있다. 이 경우 유효한 크기의 개수와 가장 큰 크기를 모두 0으로 출력한다. 크기 1은 허용 범위에 포함되어 있다면 다른 크기와 동일하게 후보로 취급한다.

입력

첫째 줄에 정수 N, L, R이 공백으로 구분되어 주어진다. 1≤N≤100,000, 1≤L≤R≤1,000,000,000이다.
둘째 줄에 각 대화방의 기록 개수를 나타내는 정수 A₁, A₂, …, Aₙ이 공백으로 구분되어 주어진다. 1≤Aᵢ≤1,000,000,000이다.

출력

유효한 묶음 크기의 개수와 그중 가장 큰 크기를 공백으로 구분하여 한 줄에 출력한다. 유효한 크기가 없으면 0 0을 출력한다.

3 2 8
24 36 60

4 6

2 3 10
14 25

0 0

1 6 6
36

1 6

출처: Devin.KR 자체 제작