주차장 경계판 규격

문제

한 주차장이 주차 구역의 경계를 표시하기 위해 여러 직선 구간에 경계판을 설치하려 한다. 설치할 구간은 모두 N개이며, i번 구간의 길이는 L_i센티미터다. 각 구간은 서로 떨어져 있으므로 한 구간에 설치한 경계판을 다른 구간까지 이어서 사용할 수 없다. 구간의 길이는 모두 양의 정수로 주어진다. 관리자는 유지 보수를 쉽게 하기 위해 모든 경계판의 길이를 하나의 규격으로 통일하려 한다. 경계판 한 개의 길이를 D센티미터로 정하면, 각 구간의 시작점부터 끝점까지 길이 D인 경계판을 빈틈없이 이어 붙여야 한다. 경계판이 서로 겹치거나 구간 밖으로 튀어나와서는 안 된다. 경계판을 잘라 쓰는 것도 허용하지 않으며, 길이가 남는 부분을 별도의 재료로 채울 수도 없다. 경계판의 폭이나 두께는 이번 작업에서 고려하지 않는다. 규격 D는 양의 정수여야 한다. 예를 들어 길이가 12센티미터인 구간에는 길이가 3센티미터인 경계판 네 개를 설치할 수 있지만, 길이가 5센티미터인 경계판으로는 그 구간을 완성할 수 없다. 하나의 구간에서 사용할 수 있는 규격이라도 다른 구간에서 사용할 수 없다면 전체 작업의 규격으로 선택할 수 없다. 관리자는 조건을 만족하는 규격 중 가장 긴 것을 선택한다. 규격을 정한 뒤에는 각 구간에 필요한 경계판 개수를 계산하여 모두 합친 수량만큼 주문한다. 경계판 길이가 1센티미터인 규격은 항상 사용할 수 있으므로 선택 가능한 규격은 반드시 존재한다. 선택해야 할 경계판의 길이와 전체 주문 수량을 구해야 한다. 구간들의 입력 순서는 규격이나 주문 수량에 영향을 주지 않는다.

입력

첫째 줄에 정수 N이 주어진다.
둘째 줄에 정수 L_1, L_2, ..., L_N이 공백으로 구분되어 주어진다.
1 ≤ N ≤ 90,000
1 ≤ L_i ≤ 999

출력

선택한 경계판 길이 D와 전체 주문 수량을 공백으로 구분하여 한 줄에 출력한다. D는 모든 구간을 조건에 맞게 채울 수 있는 가장 큰 양의 정수다.

4
18 30 42 24

6 19

3
7 10 13

1 30

1
25

25 1

출처: Devin.KR 자체 제작