Największy pół-dzielnik

To zadanie pochodzi z Codeforces. Tam też znajdują się testy do zadania.
Jeśli Twoje rozwiązanie zostanie pozytywnie ocenione na tamtych testach, należy wysłać tu zgłoszenie wypisujące "Zrobione".

Limit pamięci: 256MB

Mamy dany ciąg n liczb a_i. Znajdź największe g takie, że conajmniej połowa liczb z ciągu jest podzielna przez g.

Wejście

W pierwszym wieszu znajduje się liczba całkowita n (n<=106) oznaczająca długość ciągu.
W następnym wierszu podane jest n liczb oznaczających kolejne liczby w ciągu (a_i<=1012).

Wyjście

Na wyjście wypisz szukaną liczbę g.

Przykład

Wejście:
6
6 2 3 4 5 6

Wyjscie:
3
Wejście:
5
5 5 6 10 15

Wyjscie:
5