题目描述

小 A 有一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$。他可以选择一个区间 $[l,r]$ 满足其最大值与最小值的差不超过 $k$。

他还需找出 $m$ 个互不相同的整数 $p_1,p_2,\cdots,p_m$，满足：

• $m$ 为正整数。
• $\prod\limits_{i=l}^ra_i=\prod\limits_{i=1}^mp_i$。即选择区间的乘积等于这 $m$ 个数的乘积。
• $p_i$ 为一个质数的正整数次幂。

这 $m$ 个数的约数个数之和就是小 A 的得分。帮他求出得分的最大值。

输入格式

第一行两个整数 $n,k$。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 表示这个序列。

输出格式

一行一个整数表示答案。

4 2
6 4 2 3

7

5 3
8 6 9 6 4

13

17 17
29 38 9 10 16 5 1 10 27 20 11 9 15 11 2 3 10 

17

提示

「样例说明」

样例 $1$：选择区间 $[1,2]$，再选择 $p_1=2$，$p_2=3$，$p_3=4$，可以达到最大值 $7$，方案不唯一。

样例 $2$：选择区间 $[1,4]$，再选择 $p_1=4$，$p_2=8$，$p_3=3$，$p_4=27$，可以达到最大值 $13$。

「数据范围与约定」

本题采用捆绑测试。

• Subtask 1（1 points）：$n=1$ 且 $a_1$ 为质数。
• Subtask 2（9 points）：$n=1$。
• Subtask 3（20 points）：$n\leq 10$，$a_i \leq 20$。
• Subtask 4（13 points）：$n\leq 200$，$a_i \leq 200$。
• Subtask 5（17 points）：$n\leq 2\times 10^3$。
• Subtask 6（15 points）：$a_i$ 为质数。
• Subtask 7（25 points）：无特殊限制。

对于 $100\%$ 的数据：$1 \leq n \leq 10^5$，$2 \leq a_i \leq 10^5$，$0 \leq k \leq 10^5$。

「题目来源」

Sweet Round 05 B。
idea & solution：ET2006。