Minimizing Prime Operation Distance

We define the distance between any two positive integers (a) and (b) as the minimum number of operations required to transform (a) into (b). An operation consists of either multiplying by a prime number or dividing by a prime number (provided the division is exact). Formally, if (a = \prod_{p \in P} p^{\alpha_p}) and (b = \prod_{p \in P} p^{\beta_p}), then [ d(a,b)=\sum_{p\in P}|\alpha_p-\beta_p|. ]

Given a sequence of (n) positive integers (a_1,a_2,\dots,a_n), your task is to find a positive integer (x) that minimizes the total distance [ F(x)=\sum_{i=1}^{n}d(a_i,x). ] It turns out that the optimal (x) can be constructed by considering each prime independently. For every prime (p) that appears in the factorization of any (a_i), let (\alpha_{i,p}) be the exponent of (p) in (a_i) (taking it to be 0 if (p) does not divide (a_i)). The optimal exponent for (p) is then the median of ({\alpha_{1,p},\alpha_{2,p},\dots,\alpha_{n,p}}) (if (n) is even, you may choose the lower median). Finally, the optimal (x) is given by [ x=\prod_{p}p^{m_p}, ] where (m_p) is the median exponent for prime (p) and the total cost is the sum of (|\alpha_{i,p}-m_p|) over all primes and all (i).

Output the computed integer (x) and the corresponding minimum total number of operations.

inputFormat

The first line contains an integer (n) ((1\le n\le 10^5)). The second line contains (n) positive integers (a_1,a_2,\dots,a_n) separated by spaces.

outputFormat

Output two integers separated by a space: the optimal integer (x) and the minimum total number of operations required.

sample

3
1 2 3

1 2