D. Ghd
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Джон Доу предложил своей сестре Джейн Доу найти gcd некоторого набора чисел a.

Gcd — это целое положительное число g такое, что все числа из набора делятся на g нацело и не существует g' (g' > g), такого, что все числа набора делятся на g' нацело.

К сожалению, Джейн не смогла справиться с заданием и Джон предложил ей найти ghd того же набора чисел.

Ghd — это целое положительное число g такое, что не менее половины чисел из набора делятся на g нацело и не существует g' (g' > g), такого, что не менее половины чисел из набора делятся на g' нацело.

С таким заданием Джейн справилась всего за два часа. Попробуйте и вы.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 106) — количество чисел в наборе a. Во второй строке через пробел записаны целые числа a1, a2, ..., an (1 ≤ ai ≤ 1012). Обратите внимание, среди чисел могут быть одинаковые.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать спецификатор %I64d.

Выходные данные

Выведите единственное число g — ghd набора a.

Примеры
Входные данные
6
6 2 3 4 5 6
Выходные данные
3
Входные данные
5
5 5 6 10 15
Выходные данные
5