남김없는 묶음 포장

문제

온라인 쇼핑몰이 창고에 남은 상품을 묶음 단위로 판매하려 한다. 판매 대상은 서로 다른 N종류의 상품이며, 각 종류의 재고 수량은 양의 정수로 주어진다. 쇼핑몰은 포장 규격을 단순하게 유지하기 위해 모든 상품에 하나의 묶음 크기 g를 공통으로 적용하기로 했다. 묶음 하나에는 반드시 같은 종류의 상품 g개만 들어간다. 서로 다른 종류를 섞어 하나의 묶음을 만들 수 없으며, 어느 상품에도 다른 묶음 크기를 적용할 수 없다. 예를 들어 어떤 상품의 재고가 24개이고 g가 6이면 그 상품으로 정확히 4개의 묶음을 만든다. 재고가 25개라면 같은 크기로 모두 포장할 수 없으므로 g가 6인 규격은 사용할 수 없다. 이번 판매에서는 낱개 상품과 구별되는 묶음 상품을 만들려 하므로 g는 2 이상의 정수여야 한다. 또한 판매 대상 재고를 하나도 남기지 않아야 한다. 상품을 추가로 들여오거나 일부를 제외하는 일은 없고, 포장 과정에서 상품이 사라지거나 늘어나지도 않는다. 따라서 선택한 g로 모든 종류의 재고를 각각 정확히 나눌 수 있어야 한다. 조건을 만족하는 묶음 크기가 여러 개라면 쇼핑몰은 그중 가장 큰 값을 선택한다. 이때 완성되는 묶음의 총개수도 함께 집계하려 한다. 총개수는 상품 종류별로 만들어지는 묶음 수를 모두 더한 값이며, 한 종류의 묶음을 다른 종류와 합쳐 세지 않는다. 조건을 만족하는 g가 전혀 없다면 이번 묶음 판매를 진행하지 않는다. 재고 수량을 바탕으로 선택할 묶음 크기와 총 묶음 수를 구한다.

입력

첫째 줄에 상품 종류의 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 100,000이다.
둘째 줄에 각 종류의 재고 수량을 나타내는 정수 a_1, a_2, …, a_N이 공백으로 구분되어 주어진다. 1 ≤ a_i ≤ 1,000,000,000이다.

출력

조건을 만족하는 가장 큰 묶음 크기 g와 완성되는 묶음의 총개수를 공백으로 구분하여 한 줄에 출력한다. 조건을 만족하는 묶음 크기가 없으면 0 0을 출력한다.

3
18 30 42

6 15

2
8 15

0 0

1
49

49 1

출처: Devin.KR 자체 제작