[Usaco2004 Open]The Cow Lineup 奶牛序列

时间限制:10s      空间限制:128MB

题目描述

    约翰的N(1≤N≤100000)只奶牛站成了一列.每只奶牛都写有一个号牌,表示她的品种,号牌上的号码在1…K(1≤K≤10000)范围内.比如有这样一个队列
    1,5,3,2,5,3,4,4,2,5,1,2,3
根据约翰敏锐的数学神经,他发现一些子序列在这个队列里出现,比如3,4,1,3,而另一些没有.子序列的各项之间穿插有其他数,也可认为这个子序列存在, 现在,他想找出一个最短的子序列(由1..K组成),使之不在奶牛序列里出现.达个子序列的长度是多少呢?


输入格式

 
    第1行输入两个整数N和K,接下来N行输入奶牛序列.


输出格式

 
    最短的不出现子序列.


样例输入

14 5
1
5
3
2
5
1
3
4
4
2
5
1
2
3
 

样例输出

    3
样例说明
    所有的长度为1和为2的子序列都出现.长度为3的序列“2,2,4”不出现

提示

没有写明提示


题目来源

Green