I Hate Overlaps

Interview

Time limit1sMemory limit1024 MB

Summary

Given a sequence and a limit K, find the length of the longest contiguous subarray where no value appears more than K times.

Level: Medium5 of 10
Topics: Sliding window, Two pointers, Hash map, Array
Solved: No attempts yet

Problem

Dohyun has a case of "hongdae disease" and hates overlaps. In particular, he hates sequences that contain several copies of the same element. For Dohyun, you want to find the length of the longest contiguous subsequence that contains at most $K$ copies of any one element.

You are given a sequence of length $N$ made of positive integers at most $100\,000$ . Write a program that finds the length of the longest contiguous subsequence containing at most $K$ copies of any one integer.

Input

The first line gives the integers $N$ ( $1 \le N \le 200\,000$ ) and $K$ ( $1 \le K \le 100$ ).

The second line gives ${a_1, a_2, ... a_n}$ ( $1 \le a_i \le 100\,000$ ).

Output

Print the length of the longest contiguous subsequence that satisfies the condition.

Notes

A contiguous subsequence is a subsequence formed by selecting one or more consecutive elements of the sequence.

When $a = {3, 9, 7, 6, 5}$ , $9, 7, 6$ is a contiguous subsequence and $3, 6, 5$ is not.

Examples2

Example 1
Input
```
9 2
3 2 5 5 6 4 4 5 7
```
Expected output
```
7
```
Example 2
Input
```
10 1
1 2 3 4 5 6 6 7 8 9
```
Expected output
```
6
```