CF1292D.Chaotic V.

Æsir - CHAOS

Æsir - V.

"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 \gt 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$.

Æsir - 混沌

Æsir - V.

“一切均已规划完毕，再无隐忧。Cytus 的状态亦臻于完美。

当前时刻…… 00:01:12……

是时候了。”

情感样本现已充足。历经近三年，艾薇（Ivy）终于到了唤醒她缔结契约的姐妹——凡妮莎（Vanessa）的时刻。

A.R.C. 图书馆核心内部的系统可建模为一个具有无限多个处理节点的无向图，各节点编号为全体正整数（$1, 2, 3, \ldots$）。对任一编号为 $x$（$x > 1$）的节点，它与编号为 $\frac{x}{f(x)}$ 的节点直接相连，其中 $f(x)$ 表示 $x$ 的最小质因数。

凡妮莎的意识被分割为 $n$ 个碎片。由于长达五百余年的昏迷，这些碎片已四散：第 $i$ 个碎片当前位于编号为 $k_i!$（即 $k_i$ 的阶乘）的节点上。

为最大化成功唤醒的概率，艾薇决定将情感样本集中放置于某一节点 $P$，使得所有碎片到 $P$ 的路径长度之和最小。若多个碎片位于同一节点，则该节点到 $P$ 的路径长度需按碎片数量重复计入。

在零与一构成的世界中，这一要求对艾薇而言轻而易举。不到一秒钟后，她便已确定了这样的节点 $P$。

但对你这样一名普通人类而言，这仍有可能实现吗？

为简化问题，请你仅输出所有碎片到情感样本汇集节点 $P$ 的路径长度之和的最小值。

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!$.

第一行包含一个整数 $n$（$1 \le n \le 10^6$）—— 表示凡妮莎心智碎片的数量。

第二行包含 $n$ 个整数：$k_1, k_2, \ldots, k_n$（$0 \le k_i \le 5000$），表示凡妮莎心智碎片所在节点的编号：第 $i$ 个碎片位于编号为 $k_i!$ 的节点上。

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.

输出一个整数，表示所有碎片到存放情绪样本的节点（即节点 $P$）的路径长度之和的最小值。

需要提醒的是，若同一节点上存在多个碎片，则该节点到 $P$ 的距离也需被重复计算多次。

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$.

考虑系统的前 $24$ 个节点，节点网络结构如下所示（节点 $1!$、$2!$、$3!$、$4!$ 以粗体标出）：

对于第一个样例，Ivy 将情绪样本放置在节点 $1$ 上。由此可得：

• Vanessa 的第一段碎片到节点 $1$ 的距离为 $1$；
• Vanessa 的第二段碎片到节点 $1$ 的距离为 $0$；
• Vanessa 的第三段碎片到节点 $1$ 的距离为 $4$。

总路径长度为 $5$。

对于第二个样例，组装节点为 $6$。由此可得：

• Vanessa 的第一段碎片到节点 $6$ 的距离为 $0$；
• Vanessa 的第二段碎片到节点 $6$ 的距离为 $2$；
• Vanessa 的第三段碎片到节点 $6$ 的距离为 $2$；
• Vanessa 的第四段碎片到节点 $6$ 的距离也为 $2$。

总路径长度为 $6$。