[일반 프로그래밍 문제] 근묵자흑 - 코딩 테스트 응시 환경 체험하기
Quiz Info
[일반 프로그래밍 문제] 근묵자흑
100points


근묵자흑이라는 말이 있다. "검은 먹을 가까이 하면 검어진다". 이는 좋지 못한 사람과 가까이 하면 악에 물들게 된다고 해석할 수 있다. 이는 사람 뿐만 아니라 숫자도 마찬가지이다. 여러 숫자들을 한 곳에 모아두면 시간이 흘러 모든 숫자가 그 중 가장 작은 수에 맞춰 변하게 된다.

현재 1부터 N까지의 정수가 한 번씩 등장하는 길이 N의 수열이 있다. 여기서 당신은 연속된 K개의 정수를 골라서 한 곳에 잠시 모아둘 수 있다. 시간이 지나면 당신이 고른 K개의 정수들은 K개 중 가장 작은 정수가 된다. 이 시간은 고려하지 않는다. 여기서 이 수열을 모두 같은 수로 만들고자 할 때 최소 몇 번 골라야 하는지 구하는 프로그램을 작성하시오.

예를 들어 4개의 수가 [2, 3, 1, 4]와 같이 있고 K=3일 때, [2, 3, 1, 4]을 고르게 되면 세 수는 2, 3, 1 중 가장 작은 수인 1로 변하게 된다. 이후 [1, 1, 1, 4]가 된다. 아직 4가 남아있으니 [1, 1, 1, 4]를 고르게 되면 [1, 1, 1, 1]이 되고 총 2번만에 모두 같은 수로 만드는 데 성공이다.


입력 형식

첫 줄에 공백으로 구분된 두 정수 N, K가 차례로 주어진다.

  • N은 수열의 길이를 나타내는 2 이상 10만 이하의 자연수다.
  • K는 한 번에 연속적으로 골라야 하는 정수의 개수를 나타내는 2 이상 N 이하의 자연수다.

두 번째 줄에는 공백으로 구분된 N개의 정수가 주어진다.

  • 각 정수는 1부터 N까지의 정수 중 하나이며, 같은 정수가 두 번 이상 나타나지 않는다.


출력 형식

주어진 수열을 모두 같은 수로 만들고자 할 때 골라야 하는 최소 횟수를 출력한다.

Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
43
2314
Output
2
Example 2
Input
83
73184625
Output
4
Example 3
Input
374
31362030196133291125782243418261523283719214321416101227223551733
Output
12
⋇ Please keep the input and output formats carefully