공연장 통로의 안내띠

문제

공연장 관리팀은 관객이 이동할 통로의 가장자리에 안내띠를 붙이려 한다. 통로는 여러 구간으로 나뉘어 있으며, 각 구간의 길이는 양의 정수 미터로 측정되어 있다. 관리팀은 보관과 교체를 간단하게 하기 위해 모든 안내띠 조각의 길이를 하나로 통일하려 한다. 조각의 길이 역시 양의 정수 미터여야 한다. 한 구간에는 안내띠 조각을 처음부터 끝까지 빈틈없이 이어 붙인다. 조각을 자르거나 겹쳐 붙이는 것은 허용하지 않는다. 또한 구간 사이에는 출입문이나 방향 전환 지점이 있으므로, 하나의 조각이 두 구간에 걸쳐 놓일 수 없다. 따라서 길이가 d인 조각을 선택했다면 모든 구간의 길이가 각각 d의 배수여야 한다. 구간마다 사용하는 조각의 수는 달라도 되지만, 조각 한 개의 길이는 반드시 같아야 한다. 관리팀은 이 조건을 만족하는 길이 중 가장 긴 길이를 선택한다. 길이가 긴 조각을 사용하면 교체할 때 확인해야 하는 연결 지점이 줄어들기 때문이다. 예를 들어 길이가 8미터인 구간과 12미터인 구간에는 길이 4미터인 조각을 각각 두 개와 세 개 붙일 수 있다. 길이 8미터인 조각은 두 번째 구간을 정확히 덮을 수 없으므로 선택할 수 없다. 모든 구간의 길이가 정수이므로 길이 1미터인 조각은 언제나 사용할 수 있다. 따라서 가능한 조각 길이가 없는 경우는 없다. 구간이 하나뿐인 경우에도 같은 규칙을 적용하며, 그 구간 전체를 하나의 조각으로 덮을 수 있다. 가장 긴 조각의 길이와, 그 길이의 조각으로 모든 구간을 덮는 데 필요한 조각 수의 합을 구해야 한다. 같은 길이가 여러 구간에서 반복되어도 각 구간을 모두 따로 덮어야 한다.

입력

첫째 줄에 구간의 수인 정수 N이 주어진다. 1≤N≤100,000이다.
둘째 줄에 각 구간의 길이 A1, A2, …, AN이 공백으로 구분되어 주어진다. 모든 Ai는 정수이며 1≤Ai≤999이다.

출력

선택할 수 있는 가장 긴 조각의 길이와 필요한 전체 조각 수를 공백으로 구분하여 한 줄에 출력한다.

3
6 10 14

2 15

3
12 18 30

6 10

1
7

7 1

출처: Devin.KR 자체 제작