Hiring Admins 2: Compatibility

enigma is hiring new admins to maintain PNOJ while he goes on vacation to Wuhan during the break!


There are \(N\) people applying for staff, each of which is given an integer rating \(S_i\) of how competent they are.


Rather than choosing the most skilled people, enigma would like to choose at least \(\left\lceil\frac{N}{2}\right\rceil\) people such that the compatibility between all of the people is highest.


The compatibility of two people are determined by the greatest common divisor of the competence of the two people. Note that compatibility is commutative and associative.


Help enigma determine a subset of at least \(\left\lceil\frac{N}{2}\right\rceil\) people such that their compatibility is maximum!


Input Specification


The first line will contain \(N\) (\(1\le N\le 1000\)).

The next line will contains \(N\) space-separated integers, the \(i\)th of which is \(S_i\) (\(1\le S_i\le 10000\)).


Output Specification


Output the maximum compatibility of a subset of the \(N\) people, where the size of the subset is at least \(\left\lceil\frac{N}{2}\right\rceil\).


Sample Input


10
6207 6029 8675 1554 4938 4052 3730 9615 5082 1771


Sample Output


3


Sample Explanation:


enigma can choose the people with skills 6207, 8675, 1554, 4938, and 9615.

Comments
  • There are no comments.