Candy Rush

Interview

Time limit2.5sMemory limit1024 MB

Summary

Find the longest contiguous block of candies that contains exactly K brands, with each brand appearing the same number of times.

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

Problem

It is rush hour! You have finished work and need to buy candies for every family member before the mall closes.

Your family values exclusivity and uniformity. Each family member must receive candies from a single brand, and no other member may receive candies from that brand. Each member must also receive the same number of candies, since you do not want to show a preference for anyone.

The mall sells candies from $K$ different brands, and your family has exactly $K$ members. This may look easy, but there is a catch.

The candies are displayed on one shelf. You do not have time to pick candies one by one, so you buy one contiguous block. If you buy two candies, you must also buy every candy between them on the shelf.

What is the maximum number of candies you can buy?

Input

The first line contains two integers $N$ and $K$ ( $1 \le N, K \le 4 \times 10^5$ ). $N$ is the number of candies on the shelf, and $K$ is the number of family members. Brands are identified by distinct integers from 1 to $K$ .

The second line contains $N$ integers $C_1, C_2, \ldots, C_N$ ( $1 \le C_i \le K$ ), the brand of each candy in left-to-right order on the shelf.

Output

Print a single line with the maximum number of candies you can buy. No family member may receive two different brands, and no brand may go to two different members. Each member must receive the same number of candies, and the purchased candies must form one contiguous block on the shelf.

Examples3

Example 1
Input
```
6 2
2 2 1 1 2 2
```
Expected output
```
4
```
Example 2
Input
```
7 3
2 1 2 1 2 2 3
```
Expected output
```
0
```
Example 3
Input
```
3 4
3 4 2
```
Expected output
```
0
```