Джон Доу предложил своей сестре Джейн Доу найти gcd некоторого набора чисел a.
Gcd — это целое положительное число g такое, что все числа из набора делятся на g нацело и не существует g' (g' > g), такого, что все числа набора делятся на g' нацело.
К сожалению, Джейн не смогла справиться с заданием и Джон предложил ей найти ghd того же набора чисел.
Ghd — это целое положительное число g такое, что не менее половины чисел из набора делятся на g нацело и не существует g' (g' > g), такого, что не менее половины чисел из набора делятся на g' нацело.
С таким заданием Джейн справилась всего за два часа. Попробуйте и вы.
Выходные данные
Выведите единственное число g — ghd набора a.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
6 2 3 4 5 6
|
3
|
|
2
|
5
5 5 6 10 15
|
5
|