题解思路

设 cover[p] 为数组里被质数 p 整除的元素个数（计重），则最长长度
$L=\max_{p\ \text{为质数}} \text{cover}[p]$

题目内容

Tk 有一个长度为 $n$ 的序列 $a_1,a_2,…,a_n$ ，Tk 希望选择一个最大公约数不为 $1$ 的子序列进行染色，但是他还想选择的子序列长度尽可能大，Tk 找到了你，希望你告诉他可以选择染色的最长子序列长度，并告诉他这种最长的可染色子序列总共有多少种。

如果两个子序列所包含的元素值的多重集合相同，则认为它们是同一种方案(即，不区分下标位置，仅按所含数字及出现次数判断是否相同)。

【名词解释】

最大公约数(gcd)，指多个整数共有约数中最大的一个。例如， $12、18$ 和 $30$ 的公约数有 $1,2,3,6$ ，其中最大的约数是 $6$ ，因此 $gcd(12,18, 30)= 6$ 。

子序列：从原序列中删除任意个(可以为零，也可以为全部)元素后，保持剩余元素相对顺序不变得到的新序列。

第一行输入一个整数 $n(1 ≤n ≤2×10^6)$ 表表示序列长度。

第二行输入 $n$ 个整数

$a_1,a_2,…,a_n(1≦a_i≤2×10^6)$ 表示序列 $a$ ，

题目保证序列 $a$ 中的元素不全为 $1$ 。

输出两个整数，其中第一个整数表示子序列长度,第二个整数表示子序列个数。

输入

6
2 4 3 9 7 35

输出

2 3

说明

满足条件的最长子序列有 { $2, 4$ }, { $3, 9$ }, { $7, 35$ } 。