농장의 공통 포장 상자

문제

한 농장에서는 수확한 작물을 종류별로 나누어 보관하고 있다. 작물은 모두 낱개로 셀 수 있으며, 종류는 N가지이다. i번째 종류의 작물은 Aᵢ개 있다. 농장에서는 모든 작물을 출하하기 위해 한 상자에 담는 작물의 개수를 정하려고 한다. 포장에 사용할 정수 K를 하나 정하면 모든 상자에는 정확히 K개의 작물을 담아야 한다. 한 상자 안에는 한 종류의 작물만 넣을 수 있다. 종류마다 사용하는 상자의 개수는 달라도 되지만, 상자 하나에 담는 개수 K는 모든 종류에 똑같이 적용한다. 작물을 남기거나 버릴 수 없으며, 개수가 부족한 상자를 따로 출하할 수도 없다. 농장에서 사용할 수 있는 상자의 포장 개수에는 제한이 있다. K는 주어진 정수 L 이상 R 이하여야 한다. 이 범위에서 모든 작물을 규칙에 맞게 포장할 수 있는 K를 찾되, 가능한 값이 여러 개라면 가장 큰 값을 선택한다. 사용할 상자의 총개수를 별도로 입력받거나 제한하지는 않는다. 예를 들어 어떤 종류의 작물이 24개이고 K가 8이라면 그 종류는 세 상자로 포장할 수 있다. 그러나 다른 종류가 20개라면 K가 8인 방식은 사용할 수 없다. 종류가 다른 작물을 서로 합쳐 남는 개수를 채우는 것은 금지되어 있기 때문이다. 따라서 전체 작물 수를 합한 값만 보고 포장 가능 여부를 판단해서는 안 된다. 모든 작물 수가 양의 정수이므로 K가 1이면 각 작물을 한 개씩 포장할 수 있다. 다만 주어진 범위에 1이 포함되지 않을 수도 있으며, 이때는 조건을 만족하는 포장 개수가 전혀 없을 수 있다. 범위의 양 끝인 L과 R도 선택 가능한 값에 포함한다. 각 종류의 작물 수와 L, R이 주어진다. 모든 종류를 남김없이 포장할 수 있는 가장 큰 K를 출력한다. 조건을 만족하는 값이 없다면 -1을 출력한다. 가능한 값 중 최댓값을 선택하므로 별도의 동점 처리 규칙은 필요하지 않다.

입력

첫째 줄에 정수 N, L, R이 공백으로 구분되어 주어진다.
둘째 줄에 정수 A₁, A₂, …, Aₙ이 공백으로 구분되어 주어진다.
1 ≤ N ≤ 30,000이다.
1 ≤ L ≤ R ≤ 1,000,000,000이다.
모든 i에 대해 1 ≤ Aᵢ ≤ 1,000,000,000이다.

출력

조건을 만족하는 가장 큰 정수 K를 한 줄에 출력한다. 그런 정수가 없다면 -1을 출력한다.

3 4 10
24 48 72

8

2 7 8
18 30

-1

1 1 1
1

1

출처: Devin.KR 자체 제작