Find Least Possible Vulnerability

The vulnerability factor is the maximum length of a non-empty contiguous segment whose GCD is greater than 1, or 0 if there is none. You may change at most maxChange elements to any integers; minimize the vulnerability factor. A single element also counts as a contiguous segment.

输入格式

The first line contains n maxChange (1≤n≤100000, 0≤maxChange≤n), and the second line contains n integers in 1..10^9.

输出格式

Output a single integer answer.

样例 1

输入：

5 1
2 2 4 9 6

输出：

2

样例 2

输入：

3 1
4 2 4

输出：

1

样例 3

输入：

5 2
3 5 7 11 13

输出：

1

样例说明

Example 1: change the middle 4 to 1, leaving the longest bad segments 2, 2 and 9, 6 of length 2. Example 2: change the middle to 1, leaving only single-element bad segments on the left and right, so the answer is 1. Example 3: after any two changes there is still an original prime as a single element, so the optimum is 1, not the source's incorrect 0.