항공권 결제권의 액면가

문제

한 여행 작업실은 단체 여행에 사용할 항공권 N장을 예약했다. 항공권마다 최종 결제 금액이 정해져 있으며, 모든 금액은 원 단위의 양의 정수이다. 세금과 추가 요금은 이미 이 금액에 포함되어 있으므로 따로 더하거나 뺄 금액은 없다. 작업실은 예약한 항공권을 모두 같은 종류의 결제권으로 결제하려 한다. 결제권의 액면가는 작업실이 정할 수 있는 양의 정수 D원이다. 발급하는 모든 결제권의 액면가는 같아야 하며, 한 항공권을 결제할 때 여러 장의 결제권을 사용할 수 있다. 결제권의 발급 수에는 제한이 없지만, 한 장을 쪼개서 사용하거나 일부 금액만 사용하는 것은 허용되지 않는다. 사용한 결제권 한 장은 다른 항공권의 결제에 다시 사용할 수 없다. 각 항공권은 반드시 따로 결제해야 한다. 한 항공권에 사용한 결제권의 액면가 합은 그 항공권의 결제 금액과 정확히 같아야 한다. 여러 항공권의 금액을 먼저 합쳐 한꺼번에 결제할 수 없으며, 현금을 함께 내거나 남은 금액을 돌려받을 수도 없다. 예를 들어 액면가가 D원이라면 모든 항공권의 결제 금액을 D로 나누었을 때 나머지가 없어야 한다. 작업실은 위 조건을 만족하면서 결제권 한 장의 액면가를 최대한 크게 정하려 한다. 액면가를 정한 뒤에는 각 항공권에 필요한 결제권 수를 구하고, 그 수를 모두 더해 전체 발급 수를 결정한다. 금액이 같은 항공권이 여러 장 있더라도 각 항공권의 결제에 필요한 결제권을 별도로 발급해야 한다. 항공권별 결제 금액이 주어질 때, 가능한 가장 큰 액면가와 그 액면가의 결제권으로 모든 항공권을 결제하는 데 필요한 전체 결제권 수를 구하는 프로그램을 작성하라. 액면가 1원은 항상 사용할 수 있으므로 답이 없는 경우는 없다. 최대 액면가가 정해지면 필요한 전체 결제권 수 역시 하나로 정해진다.

입력

첫째 줄에 항공권 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 40000이다.
둘째 줄에 항공권별 결제 금액을 나타내는 정수 a_1, a_2, ..., a_N이 공백으로 구분되어 주어진다. 모든 i에 대해 1 ≤ a_i ≤ 999999이다.

출력

가능한 가장 큰 결제권 액면가와 필요한 전체 결제권 수를 순서대로 한 줄에 공백으로 구분하여 출력한다. 두 값 모두 정수로 출력한다.

3
840 1260 2100

420 10

3
14 25 36

1 75

1
999999

999999 1

출처: Devin.KR 자체 제작