混沌 V

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

对任意大于 $1$ 的正整数 $x$，令 $f(x)$ 表示 $x$ 的最小质因子。构造一棵以节点 $1$ 为根的无限树：节点 $x>1$ 的父亲为 $x/f(x)$。

树上有 $n$ 个关键节点。第 $i$ 个关键节点的编号为 $k_i!$，其中 $k_i$ 是非负整数，且 $0!=1!=1$。

记 $\operatorname{dist}(u,v)$ 为树上两点间的边数。请在树上选择一个节点 $P$，使

最小，并输出这个最小值。

输入格式

第一行一个整数 $n$。

第二行包含 $n$ 个整数 $k_1,k_2,\ldots,k_n$。

输出格式

输出一个非负整数，表示最小距离和。

样例输入 1

3
2 1 4

样例输出 1

5

样例输入 2

4
3 1 4 4

样例输出 2

6

样例输入 3

4
3 1 4 1

样例输出 3

6

样例输入 4

5
3 1 4 1 5

样例输出 4

11

数据范围

$1\le n\le10^6$，$0\le k_i\le5000$。