자작나무도, 마가목도…
시간 제한1초메모리 제한1024 MB
K개 수종의 묘목 수가 주어질 때, 연속한 P그루가 모두 다른 수종이 되도록 배열한 최대 길이를 구한다.
문제
도시 미관과 환경 개선을 위해 시 당국이 중심 대로의 녹화 사업 계획을 세웠다. 계획에 따르면 대로 한쪽에 (K)가지 종류의 나무를 한 줄로 심을 예정이며, 이를 위해 묘목을 구입했다. (i)번째 종류의 묘목은 (a_i)그루를 구입했다.
심은 나무 줄의 미적 완성도를 위해, 연속한 (P)그루의 나무는 모두 서로 다른 종류여야 한다. 줄에 있는 나무가 (P)그루보다 적으면 그 나무들은 모두 서로 달라야 한다.
구입한 묘목으로 심을 수 있는 미적으로 완성된 나무 줄의 최대 나무 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 두 정수 (K)와 (P)가 주어진다. (K)는 나무 종류의 수이고 (1 \le K \le 100,000), (P)는 연속해서 서로 다른 종류여야 하는 나무의 수이며 (2 \le P \le K)이다. 다음 (K)개 줄에 걸쳐 한 줄에 하나씩 정수 (a_i)가 주어진다. (a_i)는 (i)번째 종류의 묘목을 구입한 수이고 (1 \le a_i \le 10^9)이다.
출력
첫째 줄에, 어떤 순서로 나무를 심었을 때 미적 완성도를 만족하는 최대 나무 수를 출력한다.
힌트
예시에서는 나무를 예를 들어 2, 4, 3, 1, 2, 3, 1, 2 순서로 심을 수 있다.