미리듣기 묶음의 공통 조각

문제

음악 스트리밍 서비스의 편집자는 새 미리듣기 묶음을 준비하고 있다. 묶음에는 서로 구별되는 N개의 음원이 들어 있으며, 각 음원의 재생 길이는 초 단위의 양의 정수로 주어진다. 편집자는 묶음에 들어갈 모든 음원을 같은 길이의 조각으로 나누어 저장하려 한다. 조각 길이도 양의 정수 초여야 하며, 각 음원은 처음부터 끝까지 남는 부분 없이 정확히 나누어져야 한다. 서로 다른 음원의 끝부분을 이어 붙여 하나의 조각으로 만드는 것은 허용하지 않는다. 예를 들어 재생 길이가 18초와 30초인 두 음원은 모두 6초짜리 조각으로 나눌 수 있다. 그러나 한 음원이라도 조각 길이로 나눈 나머지가 0이 아니면 그 조각 길이는 사용할 수 없다. 조각 길이가 길수록 저장해야 할 조각 수가 줄어들기 때문에, 편집자는 가능한 한 긴 공통 조각 길이를 원한다. 음원의 순서를 바꾸거나 재생 길이를 늘리고 줄이는 작업은 할 수 없다. 이번 편집에서는 묶음의 구성을 조정하기 위해 음원 정확히 하나를 제외해야 한다. 제외한 음원에는 조각 분할 조건을 적용하지 않고, 나머지 N-1개 음원에만 같은 조각 길이를 적용한다. 아무 음원도 제외하지 않거나 두 개 이상을 제외하는 것은 허용하지 않는다. N은 2 이상이므로 제외한 뒤에도 음원이 적어도 하나 남는다. 하나만 남는 경우에는 그 음원의 전체 재생 길이를 조각 길이로 사용할 수 있다. 음원에는 입력 순서대로 1번부터 N번까지 번호가 붙어 있다. 재생 길이가 같은 음원이 여러 개 있어도 서로 다른 번호의 음원으로 취급한다. 제외할 음원을 잘 선택했을 때 얻을 수 있는 공통 조각 길이의 최댓값을 구한다. 그 최댓값을 얻는 제외 방법이 여러 개이면 번호가 가장 작은 음원을 제외한다. 모든 길이는 양의 정수이므로 1초짜리 조각은 언제나 사용할 수 있으며, 답이 없는 경우는 없다.

입력

첫째 줄에 음원 수 N이 주어진다. N은 2 이상 50,000 이하의 정수이다.
둘째 줄에 음원 1번부터 N번까지의 재생 길이 L_1, L_2, ..., L_N이 공백으로 구분되어 주어진다. 각 L_i는 1 이상 1,000,000 이하의 정수이다.

출력

가능한 공통 조각 길이의 최댓값과 제외할 음원의 번호를 공백으로 구분하여 한 줄에 출력한다. 최댓값을 얻는 번호가 여러 개이면 가장 작은 번호를 출력한다.

4
12 18 24 25

6 4

3
6 10 15

5 1

2
7 7

7 1

출처: Devin.KR 자체 제작