1798: 宝石

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：32 解决：11

题目描述

    在遥远的大麦哲伦星系有一颗盛产宝石的行星，这种宝石可以发出美丽的光芒因此广受宇宙公民的喜爱，现在一支地球的采矿小队来到了这颗神奇的行星并且成功开采了n颗宝石，他们准备利用这些宝石制作项链，每个项链都有一个美丽值，他们希望获得美丽值最大的项链，每一颗宝石都有一个光芒值ai(i=1..n)，项链的美丽值等于组成项链的宝石的光芒值的最大公约数 （比如由光芒值为 6，9，12宝石组成的项链的美丽值为3）。现在小队队长决定先暂时制作一个项链，当取i(i=1..n)颗宝石制做时总会对应一个最大美丽值fi(i=1...n)，现在他想知道出现次数最多fi的值(如果次数相同选fi值大的)。

输入

    第一行输入一个正整数n，第二行输入n个正整数ai(i=1..n)。

输出

    一个正整数w，表示出现次数最多的fi的值。

样例输入 复制 

6
1 2 2 4 3 6

样例输出 复制 

2

提示

n<=1e4，ai<=1e6

一个数的最大公约数即本身。

样例：i=1,选（6）f1=6；

i=2,选（6,3）f2=3；

i=3,选（2,2,4）f3=2；

i=4,选（2,2,4,6）f4=2；

i=5,选（1,2,2,3,4）f5=1；

i=6,选（1,2,2,4,3,6）f6=1；

发现i=3和i=4有fi=2，出现两次所以w=fi=2。