같은 횟수의 운동 묶음

문제

한 헬스장은 회원들이 운동 기구 앞에서 반복 횟수를 세기 쉽도록 운동 기록을 작은 묶음으로 나누어 표시하려 한다. 오늘 사용할 기록은 N개이며, 각 기록에는 한 운동을 반복해야 하는 총횟수가 양의 정수로 적혀 있다. 서로 다른 기록에 같은 총횟수가 적혀 있을 수도 있다. 기록 하나는 그 기록에 적힌 운동만을 나타내며, 다른 기록과 합치거나 반복 횟수를 주고받을 수 없다. 헬스장은 모든 기록에 공통으로 사용할 묶음 크기 x를 하나 정하려 한다. 묶음 크기가 x라면 각 기록의 총횟수를 정확히 x회씩 나누어 표시한다. 예를 들어 총횟수가 18이고 x가 6이면 6회짜리 묶음 세 개로 표시할 수 있다. 반면 총횟수가 20이면 같은 크기의 묶음만으로는 정확히 표시할 수 없다. 마지막 묶음만 작게 만들거나 총횟수보다 더 운동하도록 표시하는 것은 허용하지 않는다. 안내판에 사용할 수 있는 묶음 크기에도 제한이 있다. x는 정수여야 하며, 입력으로 주어지는 두 정수 L과 R에 대해 L ≤ x ≤ R을 만족해야 한다. 이 범위는 양 끝값을 모두 포함한다. 기록마다 별도의 묶음 크기를 선택할 수 없으므로, 정한 x 하나로 N개 기록을 모두 빠짐없이 나눌 수 있어야 한다. 각 기록에 생기는 묶음의 개수는 서로 달라도 된다. 직원은 안내판에 표시할 묶음의 수를 줄이기 위해 조건을 만족하는 x 중 가장 큰 값을 선택하려 한다. 가능한 값이 여러 개여도 가장 큰 정숫값 자체는 하나로 정해진다. 허용 범위 안에 모든 기록을 정확히 나누는 묶음 크기가 전혀 없을 수도 있다. 이때는 안내판을 만들 수 없다는 뜻으로 -1을 출력한다. 주어진 운동 기록과 허용 범위를 이용해 직원이 선택할 묶음 크기를 구하는 프로그램을 작성한다.

입력

첫째 줄에 기록 수 N과 허용 범위의 양 끝값 L, R이 주어진다. 둘째 줄에 각 기록의 총횟수 a_1, a_2, ..., a_N이 공백으로 구분되어 주어진다.
모든 입력값은 정수이며 1 ≤ N ≤ 35,000, 1 ≤ L ≤ R ≤ 1,000,000,000, 1 ≤ a_i ≤ 1,000,000,000이다.

출력

모든 a_i를 나누어떨어지게 하는 정수 x 중 L ≤ x ≤ R을 만족하는 가장 큰 값을 출력한다. 그런 값이 없으면 -1을 출력한다.

3 4 15
36 60 84

12

2 5 7
18 30

6

3 3 8
14 22 26

-1

출처: Devin.KR 자체 제작