John Doe 向他的妹妹 Jane Doe 提出求某组数字 a 的 gcd。
Gcd 是一个正整数 g,使得集合中的所有数字都可以被 g 整除,并且不存在这样的 g' (g' > g),即集合中的所有数字都可以被 g' 整除。
不幸的是,简无法完成这项任务,约翰让她找到同一数字子集的 ghd。
Ghd 是一个正整数 g,使得该集合中的至少一半的数字可以被 g 整除,并且不存在这样的 g' (g' > g) 使得该集合中的至少一半的数字可以被 g' 整除。
Jane 花了两个小时完成这项任务。请你也尝试一下。
输入
第一行包含一个整数 n (1 ≤ n ≤ 106),显示集合 a 中有多少个数字。第二行包含空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ 1012)。请注意,给定的集合可以包含相同的数字。
请不要使用 %lld 说明符来读取或写入 С++ 中的 64 位整数。最好使用 %I64d 说明符。
输出
打印单个整数 g — 集合 a 的 Ghd。
示例
输入 #1
6 6 2 3 4 5 6
输出 #1
3
输入 #2
5 5 5 6 10 15
输出 #2
5