[USACO04OPEN] The Cow Lineup
题目描述
约翰的 $ N $($ 1 \leq N \leq 100000 $)只奶牛站成了一列。每只奶牛都写有一个号牌,表示她的品种,号牌上的号码在 $ 1 \ldots K $($ 1 \leq K \leq 10000 $ )范围内。
比如有这样一个队列:1,5,3,2,5,3,4,4,2,5,1,2,3
根据约翰敏锐的数学神经,他发现一些子序列在这个队列里出现,比如"3,4,1,3",而另一些没有。子序列的各项之间穿插有其他数,也可认为这个子序列存在。现在,他想用 $1 \sim K$ 之间的整数构造一个最短的子序列,使之不在奶牛序列里出现。达个子序列的长度是多少呢?
输入输出格式
输入格式
第1行输入两个整数 $ N $ 和 $ K $ ,接下来 $ N $ 行输入奶牛序列.
输出格式
输出一行,最短的不出现子序列的长度。
输入输出样例
输入样例 #1
14 5
1
5
3
2
5
1
3
4
4
2
5
1
2
3
输出样例 #1
3
说明
样例解释:
所有长度为 $1$ 和 $2$ 的可能的子序列都出现了,但长度为 $3$ 的子序列"2,2,4"却没有出现。