Farmer Ron em Colorado constrói estação de esqui para vacas, mas o orçamento permite um teleférico. Monotrilho liga suporte inicial de concreto ao final por intermediários, cada qual altura0 sobre a terra. Aço reto liga cada par adjacente e deve ficar acima da terra em todo ponto.

Econômico, FR minimiza suportes. Mediu $N$ terrenos iguais $(2 \le N \le 5,000)$ com altura inteira $H$ $(0 \le H \le 1,000,000,000)$. Segurança exige distância adjacente no máximo $K$ unidades $(1 \le K \le N - 1)$. Aço rígido forma reta.

Ache mínimos suportes: aço todo acima ou tangente ao solo, distância horizontal adjacente no máximo $K$, suportes nos primeiro e último terrenos.

Entrada

• Linha $1$: dois inteiros separados por espaço $N$, $K$.
• Linhas $2..N+1$: linha $i+1$ contém altura inteira de terreno $i$.

Saída

• Linha $1$: inteiro, mínimo de torres sob essas condições.

Exemplos

Entrada 1

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

Saída 1

5

Nota

5 suportes em1, 5, 7, 9, 13. Aço tangente em4 lugares:1–5, 5–7, 7–9, 12–13.

4 suportes em1, 5, 9, 13 põem aço abaixo da terra5–9. Em1, 7, 13 fica acima mas7 e13 distam mais de4 horizontalmente. Não há solução menor de5 suportes com distância adjacente no máximo4.

Fonte original: https://github.com/ivankra/acm/blob/master/usaco/MAR06/prob/gold-en.htm

Autor do problema: Adam Rosenfield, 2004