CF364D.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.

约翰·多伊（John Doe）让他的妹妹简·多伊（Jane Doe）计算某组数 $a$ 的最大公约数（gcd）。

最大公约数（gcd）是一个正整数 $g$，满足：集合中所有数均可被 $g$ 整除，且不存在另一个正整数 $g'$（满足 $g' > g$），使得集合中所有数均可被 $g'$ 整除。

不幸的是，简未能完成该任务。于是约翰让她改为计算同一数集的“半数最大公约数”（ghd）。

半数最大公约数（ghd）是一个正整数 $g$，满足：集合中至少一半的数可被 $g$ 整除，且不存在另一个正整数 $g'$（满足 $g' > g$），使得集合中至少一半的数可被 $g'$ 整除。

简花了两个小时完成了该任务。请你也来尝试一下吧。

The first line contains an integer n (1 ≤ n ≤ 106) showing how many numbers are in set a. The second line contains space-separated integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 1012). 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.

第一行包含一个整数 $n$（$1 \leq n \leq 10^6$），表示集合 $a$ 中数字的个数。第二行包含 $n$ 个以空格分隔的整数 $a_1,\,a_2,\,\dots,\,a_n$（$1 \leq a_i \leq 10^{12}$）。请注意，给定集合中可能包含相等的数字。

在 C++ 中读写 64 位整数时，请勿使用 %lld 说明符，推荐使用 %I64d 说明符。

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

输出一个整数 $g$ —— 集合 $a$ 的广义最大公约数（Ghd）。