You are given an array of length .
You may delete any number of its elements. After the deletions, you must divide all remaining elements into exactly two non-empty groups. Every remaining element must belong to exactly one of the groups.
The greatest common divisor of all elements in each group must be greater than .
Find the minimum number of elements that must be deleted. If it is impossible to form such two groups, output .
The greatest common divisor of a group containing one element is equal to that element.
Delete and . The remaining elements can be divided into , whose gcd is , and , whose gcd is . No valid division can keep four elements.
Delete . The other five elements can be divided into , whose gcd is , and , whose gcd is . It is impossible to divide all six elements validly.
The element must be deleted. Also, any group containing two of the other elements has gcd , so at most two elements can remain. Keeping and as two one-element groups shows that deleting five elements is sufficient.
No deletion is needed. One valid division is and ; their gcds are and , respectively.