Longest Contiguous Block After Breed Removal

Farmer John has N cows (1 ≤ N ≤ 100,000) arranged in a row. Each cow has an integer breed ID in the range 0 to 1,000,000,000. Multiple cows may share the same breed ID. John wishes his lineup looked more impressive by having a long contiguous block of cows all with the same breed ID.

To achieve this, he is allowed to choose up to K distinct breed IDs and remove all cows with those IDs from the lineup. After the removal the cows close ranks. Your task is to determine the maximum length of a consecutive block, consisting solely of cows of the same breed ID, that can be created by such a removal.

More formally, let the original lineup be given by B(1), B(2), …, B(N). John may pick a set R of breed IDs with |R| ≤ K and remove every cow with a breed in R. Then, find the maximum number of cows with the same breed ID that appear consecutively in the resulting lineup.

The answer might be expressed mathematically as follows. For a chosen breed x (which is not removed) and a removal set R ⊆ {all breed IDs except x} with |R| ≤ K, let:

$$\text{answer} = \max_{x}\; \max\{\#\;\text{of occurrences of } x \text{ in a contiguous segment of } [B(1),\ldots,B(N)] \\text{such that } \forall i \text{ with } B(i)\neq x,\; B(i)\in R\}. $$

inputFormat

The first line contains two integers N and K (0 ≤ K ≤ N).

The second line contains N integers: B(1), B(2), ..., B(N) representing the breed IDs of the cows.

outputFormat

Output a single integer: the maximum length of a contiguous block of cows with the same breed ID that can be obtained after removing all cows of up to K chosen breed IDs.

sample

8 1
2 4 2 2 4 2 2 2

6