Milk Patterns

Time limit1sMemory limit128 MB

Summary

Given N integers, find the length of the longest contiguous subsequence that repeats at least K times, counting overlapping occurrences.

Level: Hard8 of 10
Topics: String matching, Binary search, Sorting, Array
Solved: No attempts yet

Problem

Farmer John has noticed that the quality of milk his cows produce varies from day to day. After a closer investigation he found that, although he cannot predict the next day's quality, the daily milk quality follows some regular patterns.

For a rigorous study he devised a classification scheme in which every milk sample is recorded as an integer between $0$ and $1{,}000{,}000$ inclusive, and he recorded data from a single cow over $N$ days ( $1 \le N \le 20{,}000$ ). He wants to find the longest pattern of samples that repeats identically at least $K$ times ( $2 \le K \le N$ ). Occurrences of the pattern may overlap; for example, in the sequence 1 2 3 2 3 2 3 1 the pattern 2 3 2 3 repeats twice.

Given the sequence of samples, find the length of the longest such repeating contiguous subsequence. It is guaranteed that at least one subsequence repeats at least $K$ times.

Input

Line 1: Two space-separated integers, $N$ and $K$ .
Lines 2 to $N+1$ : $N$ integers, one per line; line $i$ holds the milk quality on day $i$ .

Output

Line 1: A single integer, the length of the longest pattern that occurs at least $K$ times.

Examples3

Example 1
Input
```
8 2
1
2
3
2
3
2
3
1
```
Expected output
```
4
```
Example 2
Input
```
5 2
0
0
0
0
0
```
Expected output
```
4
```
Example 3
Input
```
6 2
1000000
0
1000000
0
1000000
0
```
Expected output
```
4
```