Контрольная без одного задания

В школе учитель составил контрольную из n заданий. Для каждого задания заранее записано число очков за «идеальное решение» — это числа a1, a2, ..., an.

Учитель хочет выкинуть ровно одно задание так, чтобы оставшиеся очки «хорошо делились» на одно и то же число как можно больше. То есть он хочет сделать НОД очков оставшихся заданий максимально возможным.

Найдите, какой максимальный НОД можно получить, если удалить ровно один элемент.

Формат ввода

Первая строка: целое число n. Вторая строка: n целых чисел a1, a2, ..., an.

Формат вывода

Одно целое число — максимальный возможный НОД всех чисел после удаления ровно одного элемента.

Ограничения

• 2 ≤ n ≤ 5000
• 1 ≤ ai ≤ 1 000 000

Пример

Ввод:

4
6 10 15 25

Вывод:

5

Ключевое наблюдение: если удалить элемент a[i], то НОД оставшихся чисел равен gcd(НОД слева от i, НОД справа от i). Потому что НОД по всем оставшимся — это НОД двух групп: a[0..i-1] и a[i+1..n-1].

Чтобы не пересчитывать НОД «с нуля» для каждого i (это было бы O(n^2)), заранее посчитаем:

• pref[i] = НОД первых i чисел (то есть a[0..i-1])
• suf[i] = НОД чисел с i до конца (то есть a[i..n-1])

Тогда для удаления i получаем за O(1): g_i = gcd(pref[i], suf[i+1]).

План:

• Считай n и массив a.
• Построй pref: pref[0]=0, далее pref[i+1]=gcd(pref[i], a[i]).
• Построй suf: suf[n]=0, далее назад suf[i]=gcd(suf[i+1], a[i]).
• Пройди все i и возьми максимум из gcd(pref[i], suf[i+1]).

Почему работает 0 в начале/конце: gcd(0, x) = x, значит крайние случаи (удаляем первый/последний) обрабатываются без отдельных if.

Сложность: O(n * log A), где A = max(ai), память O(n).

Частая ошибка: перепутать индексы в pref/suf (например, брать suf[i] вместо suf[i+1]) и случайно включить удаляемый элемент в НОД.