Number of primes on an interval
Given n
numbers, you are asked to look at all the contiguous sub-arrays of length k
and find the segment that has the maximum number of primes in it.
Input
The first line of the input contains two integers n
(1 ≤ n ≤ 50 000) and k
(1 ≤ k ≤ n).
The next line contains n
integers (1 ≤ ≤ ).
Output
The program should print the maximum number of primes in a subarray of length k
.
Examples
Input | Output |
---|---|
6 3 | 2 |
6 3 | 3 |
6 2 | 1 |
Constraints
Time limit: 10 seconds
Memory limit: 512 MB
Output limit: 1 MB