Longest Repeating Subsequence in Milk Quality

Farmer John has recorded a sequence of milk quality measurements over N days, where each measurement is an integer between 0 and 1,000,000. He has noticed that although the quality may vary unpredictably day to day, certain patterns appear repeatedly. In particular, he is interested in finding the longest contiguous subsequence that appears identically (even with overlaps allowed) at least K times.

More formally, given a sequence of N integers and an integer K, find the maximum integer L such that there exists a contiguous subsequence of length L which appears at least K times in the sequence.

The problem guarantees that there is always at least one subsequence that repeats at least K times.

The key idea to solve this problem is to perform a binary search on the possible length L (ranging from 1 to N) and to use a rolling hash (in \(\text{O}(N)\) time per check) to determine whether a contiguous subsequence of length L appears at least K times.

The rolling hash recurrence is given by:

[ H(i) = (H(i-1) \cdot \text{base} + a_i) \mod M ]

where base is a chosen constant, and M is a large modulus to avoid collisions. In many languages, 64-bit unsigned arithmetic can be used to simulate the modulus automatically.

inputFormat

The first line contains two integers, N (1 ≤ N ≤ 20,000) and K (2 ≤ K ≤ N). The second line contains N integers separated by spaces, where each integer is between 0 and 1,000,000 (inclusive), representing the milk quality measurements.

outputFormat

Output a single integer, the length of the longest contiguous subsequence that appears at least K times.

sample

8 2
1 2 3 2 3 2 3 1

4