PKU 1989. The Cow Lineup

소 정렬

Time Limit: 1000MS	Memory Limit: 30000K
Total Submissions: 3397	Accepted: 2028

설명

농부 John이 N마리의 젖소(1 <= N <= 100,000)를 한 줄로 세우려고 합니다.  각 소에는 1...K(1 <= K <=10,000)의 표식이 있는데, 이 표식으로 그 젖소의 품종을 확인할 수 있습니다. 예를 들면 14마리의 소들의 품종은 각각 다음과 같을 수 있습니다.
1 5 3 2 5 1 3 4 4 2 5 1 2 3
농부 John은 위의 수열처럼, 모든 숫자들로 이루어질 수 있는 수학적 가능성을 염두에 두었습니다. 예를 들면, 위에 있는 수열들에서 (굳이 연속적일 필요는 없는) 3 4 1 3 이라는 부분수열을 찾을 수 있다는 것입니다. 농부 John은, 그가 가진 소들의 품종들로 만드는 수열의 부분수열이 아닌, 1부터 K까지의  한 숫자로 얼마나 짧은 수열을 만들 수 있을지를 알고 싶습니다. 그가 이 궁금증을 해결할 수 있도록 도와주세요.

입력

* 1번째 줄 : 두 개의 정수 N과 K

* 2번째 줄부터 N+1번째 줄 : 2번째 줄은 1번째 소의 품종을; 3번째 줄은 2번째 소의 품종을; 그리고 계속 그렇게 나열합니다.

출력

* 1번째 줄 : 입력한 수열의 부분수열이 아닌, 가장 짧은 수열의 길이를 나타냅니다.

입력 예시

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

출력 예시

3

Hint

All the single digit 'sequences' appear. Each of the 25 two digit sequences also appears. Of the three digit sequences, the sequence 2, 2, 4 does not appear. 

Source

USACO 2004 U S Open




p.s: 오래간만에 하니 영 어색하고 안풀리네요. 대체 어디서 해석이 잘못된건지 손봐주실 분? (..) 원래대로면 제가 최대한 말이 되게 만들고 나서 올려야 하지만 너무 늦어서 일단 문제 먼저 올리는 뻔뻔함을 가져보렵니다 (-)