A9198 | Ghd

John Doe offered his sister Jane Doe find the gcd of some set of numbers $a$ .

Gcd is a positive integer $g$ , such that all number from the set are evenly divisible by $g$ and there isn't such $g'$ $(g'>g)$ , that all numbers of the set are evenly divisible by $g'$ .

Unfortunately Jane couldn't cope with the task and John offered her to find the ghd of the same subset of numbers.

Ghd is a positive integer $g$ , such that at least half of numbers from the set are evenly divisible by $g$ and there isn't such $g'$ $(g'>g)$ that at least half of the numbers from the set are evenly divisible by $g'$ .

Jane coped with the task for two hours. Please try it, too.

The first line contains an integer $n$ ( $1<=n<=10^{6}$ ) showing how many numbers are in set $a$ . The second line contains space-separated integers $a_{1},a_{2},...,a_{n}$ $(1<=a_{i}<=10^{12})$ . Please note, that given set can contain equal numbers.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the %I64d specifier.

Print a single integer $g$ — the Ghd of set $a$ .