Farmer Ron en Colorado construye una estación de esquí para vacas, pero el presupuesto permite un solo remonte. El monorraíl une soporte inicial de hormigón al final mediante intermedios, cada uno de altura0 sobre su suelo. Acero recto une cada par adyacente y debe quedar sobre el suelo en todos sus puntos.

El ahorrador FR minimiza soportes. Midió $N$ parcelas iguales $(2 \le N \le 5,000)$ con altura entera $H$ $(0 \le H \le 1,000,000,000)$. Seguridad exige distancia adyacente no mayor de $K$ unidades $(1 \le K \le N - 1)$. Acero rígido forma línea recta.

Calcula mínimos soportes: acero totalmente sobre el suelo o tangente, distancia horizontal adyacente no mayor de $K$, soporte en primera y última parcela.

Entrada

• Línea $1$: dos enteros separados por espacio $N$, $K$.
• Líneas $2..N+1$: línea $i+1$ tiene altura entera de parcela $i$.

Salida

• Línea $1$: entero, mínimo de torres bajo esas condiciones.

Ejemplos

Entrada 1

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

Salida 1

5

Nota

5 soportes en1, 5, 7, 9, 13. Acero tangente en4 lugares:1–5, 5–7, 7–9, 12–13.

4 soportes en1, 5, 9, 13 dejan acero bajo tierra5–9. En1, 7, 13 queda sobre tierra pero7 y13 distan más de4 horizontalmente. No hay solución menor de5 soportes con distancias adyacentes no mayores de4.

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

Autor del problema: Adam Rosenfield, 2004