Colorado의 Farmer Ron은 소를 위한 스키장을 만드는데 예산상 리프트는 하나뿐입니다. 모노레일이 시작 콘크리트 지지대를 중간 지지대를 통해 끝과 연결하며 각각 지면 위 높이가0입니다. 이웃 지지대를 곧은 강철로 잇고 모든 점이 지면 위에 있어야 합니다.

절약가 FR은 지지대를 최소화합니다. 같은 크기 땅 $N$개 $(2 \le N \le 5,000)$의 정수 높이 $H$ $(0 \le H \le 1,000,000,000)$을 조사했습니다. 안전상 이웃 간격은 $K$단위 이하 $(1 \le K \le N - 1)$입니다. 강철은 단단한 직선입니다.

강철이 모두 지면 위 또는 접하고, 이웃 수평 간격이 $K$ 이하, 첫 땅과 마지막 땅에 지지대가 있는 최소 수를 구하세요.

입력

• $1$행: 공백으로 구분한 두 정수 $N$, $K$.
• $2..N+1$행: $i+1$행은 땅 $i$의 정수 높이입니다.

출력

• $1$행: 조건을 만족하는 최소 지지대 수인 정수.

예제

입력 1

13 4
0
1
0
2
4
6
8
6
8
8
9
11
12

출력 1

5

참고

1, 5, 7, 9, 13에5개 지지대를 만듭니다. 강철은1–5, 5–7, 7–9, 12–13 네 곳에서 접합니다.

1, 5, 9, 13에4개면5–9에서 땅 아래입니다. 1, 7, 13에서는 강철이 위지만7과13의 수평 간격이4 초과입니다. 이웃 간격4 이하이며5개 미만인 해는 없습니다.

원문 출처: https://github.com/ivankra/acm/blob/master/usaco/MAR06/prob/gold-en.htm

문제 작성자: Adam Rosenfield, 2004