Chaotic V.
Contest: Codeforces Round 614 (Div. 1)
Difficulty rating: 2700
Tags: dp, graphs, greedy, math, number theory, trees

"Everything has been planned out. No more hidden concerns. The condition of Cytus is also perfect.

The time right now...... 00:01:12......

It's time."

The emotion samples are now sufficient. After almost 3 years, it's time for Ivy to awake her bonded sister, Vanessa.

The system inside A.R.C.'s Library core can be considered as an undirected graph with infinite number of processing nodes, numbered with all positive integers ($$$1, 2, 3, \ldots$$$). The node with a number $$$x$$$ ($$$x > 1$$$), is directly connected with a node with number $$$\frac{x}{f(x)}$$$, with $$$f(x)$$$ being the lowest prime divisor of $$$x$$$.

Vanessa's mind is divided into $$$n$$$ fragments. Due to more than 500 years of coma, the fragments have been scattered: the $$$i$$$-th fragment is now located at the node with a number $$$k_i!$$$ (a factorial of $$$k_i$$$).

To maximize the chance of successful awakening, Ivy decides to place the samples in a node $$$P$$$, so that the total length of paths from each fragment to $$$P$$$ is smallest possible. If there are multiple fragments located at the same node, the path from that node to $$$P$$$ needs to be counted multiple times.

In the world of zeros and ones, such a requirement is very simple for Ivy. Not longer than a second later, she has already figured out such a node.

But for a mere human like you, is this still possible?

For simplicity, please answer the minimal sum of paths' lengths from every fragment to the emotion samples' assembly node $$$P$$$.

Input format:
The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — number of fragments of Vanessa's mind.

The second line contains $$$n$$$ integers: $$$k_1, k_2, \ldots, k_n$$$ ($$$0 \le k_i \le 5000$$$), denoting the nodes where fragments of Vanessa's mind are located: the $$$i$$$-th fragment is at the node with a number $$$k_i!$$$.

Output format:
Print a single integer, denoting the minimal sum of path from every fragment to the node with the emotion samples (a.k.a. node $$$P$$$).

As a reminder, if there are multiple fragments at the same node, the distance from that node to $$$P$$$ needs to be counted multiple times as well.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
Considering the first $$$24$$$ nodes of the system, the node network will look as follows (the nodes $$$1!$$$, $$$2!$$$, $$$3!$$$, $$$4!$$$ are drawn bold):

For the first example, Ivy will place the emotion samples at the node $$$1$$$. From here:

- The distance from Vanessa's first fragment to the node $$$1$$$ is $$$1$$$.
- The distance from Vanessa's second fragment to the node $$$1$$$ is $$$0$$$.
- The distance from Vanessa's third fragment to the node $$$1$$$ is $$$4$$$.

The total length is $$$5$$$.

For the second example, the assembly node will be $$$6$$$. From here:

- The distance from Vanessa's first fragment to the node $$$6$$$ is $$$0$$$.
- The distance from Vanessa's second fragment to the node $$$6$$$ is $$$2$$$.
- The distance from Vanessa's third fragment to the node $$$6$$$ is $$$2$$$.
- The distance from Vanessa's fourth fragment to the node $$$6$$$ is again $$$2$$$.

The total path length is $$$6$$$.

Example input:
3
2 1 4

Example output:
5

Example input:
4
3 1 4 4

Example output:
6

Editorial:
First of all, one can see that the network is a tree rooted at vertex $$$1$$$, thus for each pair of vertices in it there can only be one simple path.
Also, the assembly node $$$P$$$ must be on at least one simple path of a fragment to the root (proof by contradiction, explicit solution is trivial).
Let's start with $$$P$$$ being node $$$1$$$.
From here, moving down to any branch will increase $$$1$$$ for each element not being in that branch and decrease $$$1$$$ for each element being in, thus we'll only move down to the branch having the most elements until the decreasing cannot outmatch the increasing (in other words, the number of fragments in a branch must be more than half for that branch to be reached).
Given the criteria of the graph, we can see that: two nodes are in the same branch from the root if having the same one largest factor from the prime factorization, they are in the same branch from a depth-1-node if having the same two largest factors, ..., in the same branch from a depth-$$$k$$$-node if having the same $$$k+1$$$ largest factors.
Keep in mind that here the largest factors can be the duplicated, i.e. in the case of $$$576 = 2^6 \cdot 3^2$$$, the two largest factors are $$$3$$$ and $$$3$$$, and the three largest factors are $$$3$$$, $$$3$$$ and $$$2$$$.
The process will now become factorizing the numbers, and then, cycle by cycle, pop the current largest factor of each number and group them, find out the group (branch) with most occurences and either move on (if the total sum can be lowered) or stop the process.
Since all of these are factorials, the factorizing can be done with a bottom-up dynamic programming fashion.
Also, as $$$k \le 5000$$$ and $$$n \le 10^6$$$, consider grouping duplicated elements to reduce calculating complexity.
Both factorization and processing has the worst-case complexity of $$$\mathcal{O}(MAXK^2 \cdot f(MAXK))$$$, with $$$k \cdot f(k)$$$ being the estimated quantity of prime divisors of $$$k!$$$.
It's proven that $$$f(k) = M + \ln \ln k$$$, with $$$M$$$ being the Meissel-Mertens constant.
The proof of this formula is based on the fact this number is calculated through the sum of the reciprocals of the primes.