25588번 - 푸앙이와 계단 수열

문제

푸앙이는 1ドル$ 이상 9ドル$ 이하의 양의 정수로 이루어진 길이가 $N$인 수열 $A_1, A_2, \cdots, A_N$을 가지고 있으며 다음과 같은 연산을 할 수 있다.

1. 수열의 왼쪽, 혹은 오른쪽에서부터 원소를 최대 3개 삭제한다.
2. 수열의 왼쪽, 혹은 오른쪽에서부터 길이가 $K$인 계단 수열을 삭제한다.

계단 수열이란 수열의 인접한 모든 원소의 차가 1ドル$인 수열이다.

푸앙이는 여러 연산을 통해 자신이 가지고 있는 수열을 지우려 한다. 주어진 수열을 원소가 존재하지 않는 빈 수열로 만드는 데 필요한 연산의 최소 횟수를 구하시오.

입력

첫 번째 줄에 $N$ $(3 \leq N \leq 100,000円),ドル $K$ $(1 \leq K \leq N)$가 공백으로 구분되어 주어진다.

두 번째 줄에 수열 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1 \leq A_i \leq 9)$

출력

주어진 수열을 빈 수열로 만들기 위한 최소 연산 횟수를 출력하시오.

제한

힌트