버스 출발표의 공통 눈금

문제

한 버스 환승장은 여러 노선의 출발 예정 시각을 하나의 전광판에 표시하려 한다. 모든 노선은 운영을 시작하는 기준 시각에 첫 버스를 출발시킨다. 이후 각 노선은 자신에게 정해진 배차 간격만큼의 시간이 지날 때마다 다음 버스를 출발시킨다. 배차 간격은 운영 중에 바뀌지 않으며, 이 문제에서는 운행 종료 시각을 따로 두지 않는다. 전광판 담당자는 기준 시각을 0분으로 놓고 일정한 간격으로 시간 눈금을 만들려 한다. 눈금 간격을 양의 정수 d분으로 정하면 눈금은 0분, d분, 2d분, 3d분과 같이 이어진다. 모든 노선의 모든 출발 예정 시각이 이 눈금 중 하나와 정확히 일치해야 전광판에 적용할 수 있다. 어떤 눈금에 출발하는 버스가 없어도 괜찮으며, 여러 노선의 버스가 같은 눈금에서 출발해도 괜찮다. 예를 들어 배차 간격이 12분인 노선은 기준 시각으로부터 0분, 12분, 24분, 36분 뒤에 차례로 출발한다. 이 노선만 고려하면 3분 간격의 눈금을 사용할 수 있다. 반면 5분 간격의 눈금을 사용하면 12분 뒤의 출발을 눈금에 맞출 수 없다. 다른 노선도 있다면 그 노선들의 출발 예정 시각까지 모두 같은 기준으로 확인해야 한다. 눈금 간격이 클수록 전광판에 그려야 하는 눈금의 수가 적어진다. 따라서 담당자는 조건을 만족하는 눈금 간격 중 가장 큰 값을 선택하려 한다. N개 노선의 배차 간격이 주어질 때 이 값을 구한다. 모든 배차 간격이 양의 정수이므로 1분 간격은 항상 사용할 수 있다. 노선이 하나뿐인 경우에도 같은 규칙을 적용한다.

입력

첫째 줄에 노선 수 N이 주어진다. 둘째 줄에 각 노선의 배차 간격 A_1, A_2, ..., A_N이 분 단위로 공백으로 구분되어 주어진다. 모든 값은 정수이며 1 ≤ N ≤ 100,000, 1 ≤ A_i ≤ 999이다.

출력

모든 노선의 출발 예정 시각을 표시할 수 있는 가장 큰 눈금 간격을 분 단위의 정수 하나로 출력한다.

4
36 60 84 108

12

3
14 25 39

1

1
47

47

출처: Devin.KR 자체 제작