Minimum Absolute Difference of GCD and LCM Partition

You are given a multiset \(A\) of size \(n\) consisting of positive integers. The multiset \(A\) may contain duplicates. Your task is to partition \(A\) into two non-empty multisets \(S\) and \(T\) such that for every positive integer \(v\), the total count of \(v\) in \(S\) and \(T\) equals the count in \(A\). In other words, \(S\) and \(T\) form a valid partition of \(A\).

Then, define:

• \(g = \gcd_{v \in S} v\) as the greatest common divisor (GCD) of all elements in \(S\).
• \(l = \operatorname{lcm}_{v \in T} v\) as the least common multiple (LCM) of all elements in \(T\).

Your goal is to find the minimum possible value of \(|g - l|\) over all valid partitions.

Note: It is guaranteed that \(S\) and \(T\) must both be non-empty.

inputFormat

The first line contains an integer \(n\) representing the size of the multiset \(A\). The second line contains \(n\) positive integers, the elements of \(A\), separated by spaces.

outputFormat

Output a single integer: the minimum possible value of \(|\gcd(S) - \operatorname{lcm}(T)|\) among all valid partitions of \(A\) into non-empty \(S\) and \(T\).

sample

2
1 1

0