한 곡을 뺀 스트리밍 조각

문제

한 음악 스트리밍 서비스는 재생 목록의 곡들을 일정한 길이의 조각으로 나누어 전송한다. 재생 목록에는 N개의 곡이 있고, 목록에 놓인 순서대로 1부터 N까지 번호가 붙어 있다. 각 곡의 길이는 1초 이상 99초 이하의 정수다. 서비스는 전송 실험을 위해 목록에서 정확히 한 곡을 제외한 뒤, 남은 모든 곡에 같은 조각 길이를 적용하려 한다. 조각 길이 D는 양의 정수 초여야 한다. 각 곡은 자신의 시작 지점부터 길이가 정확히 D초인 조각들로 나뉜다. 곡의 마지막에 D초보다 짧은 조각이 남아서는 안 되며, 서로 다른 곡의 일부를 합쳐 하나의 조각으로 만들 수도 없다. 따라서 길이가 T초인 곡을 사용할 수 있으려면 T가 D로 나누어떨어져야 한다. 곡마다 만들어지는 조각의 개수는 달라도 된다. 서비스는 제외할 곡과 조각 길이를 함께 정하여 D를 가능한 한 크게 만들고자 한다. 제외한 곡은 전송하지 않으므로 그 곡의 길이가 D로 나누어떨어지는지는 확인하지 않는다. 나머지 곡의 순서는 유지되지만, 순서는 조각 길이의 조건에 영향을 주지 않는다. 같은 길이의 곡이 여러 개 있어도 서로 다른 번호의 곡으로 취급한다. 가장 큰 조각 길이를 만들 수 있는 제외 대상이 여러 개라면 번호가 가장 작은 곡을 제외한다. 예를 들어 서로 다른 두 곡을 각각 제외했을 때 가능한 최대 조각 길이가 같다면, 두 곡 중 목록에서 먼저 등장한 곡을 선택한다. 아무 곡도 제외하지 않거나 두 곡 이상을 제외하는 선택은 허용되지 않는다. N은 2 이상이므로 제외 후에도 적어도 한 곡이 남는다. 또한 길이가 정수인 모든 곡은 1초 조각으로 나눌 수 있으므로 가능한 선택은 항상 존재한다. 제외할 곡의 번호와 그때 사용할 수 있는 가장 큰 조각 길이 D를 구하라.

입력

첫째 줄에 정수 N이 주어진다. 2 ≤ N ≤ 100,000이다.
둘째 줄에 곡의 길이 T_1, T_2, …, T_N이 공백으로 구분되어 주어진다. 각 T_i는 1 이상 99 이하의 정수다.

출력

제외할 곡의 번호와 가장 큰 조각 길이 D를 공백으로 구분하여 한 줄에 출력한다. 가장 큰 D를 얻는 곡이 여러 개라면 가장 작은 번호를 출력한다.

4
12 18 25 30

3 6

3
8 8 8

1 8

2
7 14

1 14

출처: Devin.KR 자체 제작