该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

翁老师正在观察一个包含 $n$ 个细胞的培养样本。

每个细胞都有一个用正整数表示的活跃度。初始时，第 $i$ 个细胞的活跃度为 $a_i$。

只要培养样本中存在活跃度大于等于 $2$ 的细胞，翁老师就会重复执行以下步骤，这被称为一次操作：

• 从培养样本中选择一个活跃度大于等于 $2$ 的细胞。设所选细胞的活跃度为 $x$。
• 选择一个能整除 $x$ 的质数 $p$。
• 将该细胞从培养样本中移除，并向培养样本中加入 $p$ 个新的细胞，每个新细胞的活跃度均为 $x / p$。（由于 $p$ 是 $x$ 的约数，因此 $x / p$ 必定是一个正整数。）

每次操作会使细胞总数增加 $p - 1$。如果新加入的细胞活跃度大于等于 $2$，它们就可以在后续的操作中被选中。活跃度为 $1$ 的细胞不能被选中进行操作。

在每次操作中，翁老师可以自由决定选择哪个细胞，以及使用哪个质数 $p$。根据这些选择，直到所有细胞活跃度均变为 $1$ 所需的操作次数可能会有所不同。

请帮翁老师求出，使所有细胞的活跃度都变为 $1$ 所需的最少和最多操作次数。

输入格式

第一行输入一个整数 $n$。

第二行输入 $n$ 个空格隔开的正整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出两个整数表示答案，用空格隔开。

3
2 3 4

5 5

4
1 6 8 9

14 15

10
12 15 16 18 20 25 27 30 49 64

141 171

24
2 4 6 8 9 10 12 15 16 18 20 21 24 25 27 30 32 36 40 45 49 64 81 1000000

250346 988666

1
1

0 0

提示

数据范围

对于 $100\%$ 的数据，$1\leq n\leq 2\times 10^5$，$1\leq a_i\leq 10^6$。