Hoofball#10406
Para prepararse para el próximo torneo de hoofball, el granjero John está entrenando a sus vacas (numeradas convenientemente 1, \ldots, n) en el pase del balón. Las vacas están paradas en una fila muy larga a un lado del establo, con la vaca parada a x_i unidades de distancia del establo. Todas las vacas se encuentran en posiciones distintas.
Al comienzo del entrenamiento, el granjero John pasará varios balones a diferentes vacas. Cada vez que la vaca recibe un balón, ya sea del granjero John o de otra vaca, se lo pasa a la vaca más cercana a ella. Si varias vacas están a la misma distancia de ella, le pasa el balón a la que está más a la izquierda. Para que cada vaca tenga al menos un poco de práctica de pase, el granjero John quiere asegurarse de que cada vaca sostenga un balón al menos una vez. Ayúdalo a encontrar el número mínimo de balones que necesita repartir inicialmente para lograrlo, suponiendo que elige un conjunto inicial apropiado de vacas para recibirlos.
La primera línea contiene el entero n~(1 \le n \le 100). La segunda línea contiene enteros, donde el -ésimo entero es x_i~(1 \le x_i \le 1000).
Imprime el número mínimo de balones que el granjero John debe pasar inicialmente a las vacas para que cada vaca sostenga un balón al menos una vez.
En el ejemplo, el granjero John debe pasar un balón a la vaca en x = 1 y otro balón a la vaca en x = 11. La vaca en x = 1 le pasa su balón a la vaca en x = 3, después de lo cual este balón sigue rebotando de un lado a otro entre las vacas en x = 3 y x = 4. La vaca en x = 11 le pasa su balón a la vaca en x = 7, quien se lo pasa a la vaca en x = 4, después de lo cual este balón también sigue rebotando entre las vacas en x = 3 y x = 4. Así, cada vaca recibe un balón al menos una vez, ya sea del granjero John o de otra vaca.
Es fácil ver que no existe una única vaca a la que el granjero John pudiera pasarle un balón de manera que todas las vacas terminaran recibiéndolo.
Ejemplo 1