Maximum length of subarray with unique elements after K replacements

C++ Hard arrays

Task «Maximum length of subarray with unique elements after K replacements»

Given an array of integers. It is allowed to replace at most K elements of the array with any other integers (possibly non-unique). It is necessary to find the maximum possible length of a contiguous subarray, all elements of which are distinct (unique) after performing at most K replacements. If it is impossible to obtain a subarray with unique elements, output 0. Constraints: array length N up to 10^5, K up to N, element values modulo up to 10^9.

Input Format

In the first line, two integers N and K (1 ≤ N ≤ 100000, 0 ≤ K ≤ N). In the second line, N integers — the elements of the array.

Output Format

One integer — the maximum length of a subarray with unique elements after at most K replacements.

Examples

Example 1

INPUT

4
1 2 3 4

OUTPUT

3

main.cpp