P5093 [USACO04OPEN] The Cow Lineup

John’s $N$ cows ($1 \leq N \leq 100000$) are standing in a line. Each cow has a tag number that shows her breed, and the tag number is in the range $1 \ldots K$ ($1 \leq K \leq 10000$). For example, there is a lineup like this: 1,5,3,2,5,3,4,4,2,5,1,2,3. With his sharp math sense, John finds that some subsequences appear in this lineup, such as "3,4,1,3", while others do not. Other numbers may appear between the elements of the subsequence; if so, the subsequence is still considered to exist. Now he wants to use integers from $1 \sim K$ to construct the shortest subsequence that does not appear in the cow sequence. What is the length of such a subsequence?

The first line contains two integers $N$ and $K$. The next $N$ lines contain the cow sequence.

Output one line: the length of the shortest subsequence that does not appear.

Explanation of the sample: All possible subsequences of length $1$ and $2$ appear, but the subsequence of length $3$, "2,2,4", does not appear. Translated by ChatGPT 5