Description

Xiao A has a sequence $a_1, a_2, \cdots, a_n$ of length $n$. He can choose an interval $[l, r]$ such that the difference between its maximum value and minimum value is at most $k$.

He also needs to find $m$ pairwise distinct integers $p_1, p_2, \cdots, p_m$ such that:

• $m$ is a positive integer.
• $\prod\limits_{i=l}^r a_i = \prod\limits_{i=1}^m p_i$. That is, the product of the chosen interval equals the product of these $m$ numbers.
• Each $p_i$ is a positive integer power of a prime.

The sum of the numbers of divisors of these $m$ numbers is Xiao A's score. Help him find the maximum possible score.

Input Format

The first line contains two integers $n, k$.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ representing the sequence.

Output Format

Output one integer in a single line, the answer.

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

Hint

"Sample Explanation"

Sample $1$: Choose the interval $[1, 2]$, then choose $p_1 = 2$, $p_2 = 3$, $p_3 = 4$, and you can reach the maximum value $7$. The solution is not unique.

Sample $2$: Choose the interval $[1, 4]$, then choose $p_1 = 4$, $p_2 = 8$, $p_3 = 3$, $p_4 = 27$, and you can reach the maximum value $13$.

"Constraints and Notes"

This problem uses bundled testdata.

• Subtask 1 (1 points): $n = 1$ and $a_1$ is prime.
• 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$ is prime.
• Subtask 7 (25 points): no special restrictions.

For $100\%$ of the testdata: $1 \leq n \leq 10^5$, $2 \leq a_i \leq 10^5$, $0 \leq k \leq 10^5$.

"Source"

Sweet Round 05 B.
idea & solution: ET2006.

Input Format

Output Format

Hint

Translated by ChatGPT 5