Double Rainbow

Interview

Time limit1sMemory limit1024 MB

Summary

Given a color sequence and k colors, find the shortest contiguous block that contains every color and whose complement also contains every color, or print 0.

Level: Medium6 of 10
Topics: Two pointers, Sliding window, Prefix sum, Array
Solved: No attempts yet

Problem

Let $P$ be a set of $n$ points on the $x$ -axis, and each point is colored with one of the colors $1, 2, \dots, k$ . For each of the $k$ colors, there is at least one point in $P$ colored with that color. For a set $P'$ of consecutive points from $P$ , if both $P'$ and $P \backslash P'$ contain at least one point of each color, then $P'$ makes a double rainbow. See the figure below as an example. The set $P$ consists of ten points, and each point is colored with one of the colors $1$ , $2$ , $3$ , and $4$ . The set $P'$ of the five consecutive points inside the rectangle makes a double rainbow.

Given a set $P$ of points and the number $k$ of colors as input, write a program that computes and prints the minimum size of $P'$ that makes a double rainbow.

Input

Your program is to read from standard input. The input starts with a line containing two integers $n$ and $k$ ( $1 ≤ k ≤ n ≤ 10,000$ ), where $n$ is the number of points in $P$ and $k$ is the number of colors. Each of the following $n$ lines consists of an integer from $1$ to $k$ , inclusive, and the $i$ -th line corresponds to the color of the $i$ -th point of $P$ from the left.

Output

Your program is to write to standard output. Print exactly one line. The line should contain the minimum size of $P'$ that makes a double rainbow. If there is no such $P'$ , print 0.

Examples2

Example 1
Input
```
10 4
1
2
3
1
1
4
2
4
3
3
```
Expected output
```
5
```
Example 2
Input
```
6 3
1
1
2
2
3
3
```
Expected output
```
0
```