시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1 1 1 100.000%

문제

수열에서 몇 개의 수를 순서대로 골라 만들 수 있는 수열을 부분수열이라고 한다. 예를 들어 수열 S=[1, 5, 3, 2, 5, 1, 3, 4, 4, 2, 5, 1, 2, 3]에서 첫 번째, 다섯 번째, 일곱 번째, 열 번째 수를 고르면 부분수열 p=[1, 5, 3, 2]을 만들 수 있다.

수열 S와 임의의 부분수열 p가 주어졌을 때, 모두 몇 가지 방법으로 S에서 고른 수로 p를 구성할 수 있는지에 관한 문제는 많이 다루어진 문제이므로, 이번에는 반대의 경우를 생각해 보자. 수열 S가 주어지고, 이 수열에서 만들 수 없는 부분수열에 관해 생각해 보는 것이다.

부분수열이 충분히 길면 물론 만들어 낼 수 없을 것이다. 그럼 만들어 낼 수 없는 부분수열 중 가장 짧은 것의 길이는 얼마일까? 이를 알아내는 프로그램을 작성하라.

입력

첫 줄에 두 정수 n과 k가 주어진다. (1≤n≤100,000. 1≤k≤10,000) n은 수열 S의 길이이고, k는 수열 내에 존재하는 수들의 범위이다. 다시 말해, S가 1이상 k이하의 정수들로만 이루어져 있음을 나타낸다. 둘째 줄부터는 S를 이루는 수들이 한 줄에 한 개씩 차례로 주어진다.

출력

첫 줄에 S에 존재하지 않는 부분수열 중 가장 짧은 것의 길이를 출력한다.

예제 입력

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

예제 출력

3

힌트

1이상 5이하의 정수들로 만들 수 있고 길이가 1, 2인 수열은 모두 S 내에 부분수열로서 존재한다. 길이가 3인 부분수열 중 [2, 2, 4]는 수열 내에 존재하지 않는다.

출처

  • 문제를 번역한 사람: author5