충전기 한 대를 철거하면

문제

전기차 충전소에 충전기 N대가 한 줄로 설치되어 있다. i번째 충전기의 출력 단위는 a_i이다. 충전소 운영자는 노후한 충전기 정확히 한 대를 철거하려고 한다. 철거 후 남는 N-1대의 출력 단위의 최대공약수가 클수록 남은 충전기들을 같은 규격의 전력 모듈로 묶어 관리하기 쉽다. 따라서 운영자는 철거 후 남은 충전기들의 출력 단위의 최대공약수가 최대가 되도록 철거할 충전기를 고르려 한다. 여러 개의 정수의 최대공약수는 그 정수들을 모두 나누어떨어지게 하는 가장 큰 양의 정수이다. 철거할 충전기는 반드시 한 대여야 하며 N은 2 이상이므로 항상 한 대 이상이 남는다. 남는 충전기가 한 대이면 그 충전기의 출력 단위가 최대공약수이다. 철거 후 가능한 최대공약수의 최댓값과, 그 값을 만들 수 있는 철거 충전기 번호(1부터 시작) 중 가장 작은 번호를 구하라.

입력

첫째 줄에 충전기 수 N이 주어진다. 둘째 줄에 a_1, a_2, …, a_N이 공백으로 구분되어 주어진다. 2 ≤ N ≤ 200,000, 1 ≤ a_i ≤ 10^9 이며 모든 값은 정수이다.

출력

한 줄에 최대공약수의 최댓값과 가장 작은 철거 번호를 공백으로 구분해 출력한다.

4
12 18 30 7

6 4

3
5 5 5

5 1

2
8 12

12 1

출처: Devin.KR 자체 제작