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!

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 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\).

`10`

6207 6029 8675 1554 4938 4052 3730 9615 5082 1771

`3`

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

- Points: 15
- Time limit: 1.0s
- Memory limit: 64.0M
- Author: BattleMage_
- Category: Classics
- Type: Simple Math, Ad Hoc
- All Submissions Best Submissions

Comments

- There are no comments.