URI Online Judge | 1107

Escultura Láser

Maratón de Programación de SBC Brasil

Timelimit: 1

Desde su invención, en 1958, el láser se ha utilizado en una gran variedad de aplicaciones, como equipos electrónicos, instrumentos quirúrgicos, armas y mucho más.

La imagen de arriba muestra un diagrama de un equipo para esculpir, con un láser, un bloque de un material sólido. En la figura podemos ver un emisor láser que se mueve horizontalmente hacia la derecha y la izquierda con una velocidad constante. Cuando el emisor está encendido y se mueve, una capa de anchura específica se retira del bloque, que se vaporiza por el láser.

La imagen de abajo ilustra el proceso de esculpir con un láser, que muestra un ejemplo de (a) un bloque, con una altura de 5 mm y una longitud de 8 mm, en el inicio del proceso, (b) el formato que queremos para el bloque esculpido, y (c) la secuencia de la absorción de la capa durante el proceso, teniendo en cuenta que en cada paso, se elimina una capa de 1 mm de ancho. En el primer paso, se retira la pieza numerada 1; en el segundo, la pieza 2; y así sigue. Durante el proceso de la escultura, el láser se enciende 7 veces, en total, una vez por cada trozo extraído del bloque.


Escribir un programa que, dada la altura y la longitud del bloque, y su formato final, averiguar el número total de veces que el láser debe estar encendido.

Entrada

La entrada contiene varios casos de prueba. Cada caso de prueba se compone de dos líneas. La primera, contiene dos números enteros A y C, separadas por un espacio en blanco, lo que indica, respectivamente, la altura (1 ≤ A ≤ 104) y la longitud (1 ≤ C ≤ 104) del bloque esculpido, en milímetros. La segunda línea contiene C enteros Xi, cada uno indica la altura final, en milímetros, del bloque comprendido entre las posiciones i e i+1 a través de la longitud (0 ≤ Xi ≤ A, para 0 ≤ i ≤ C - 1). Tenga en cuenta que en cada paso, una capa de anchura de 1 mm se elimina en las partes del bloque en las que el láser está encendido.

El final de la entrada se indica por una línea que contiene sólo dos ceros, separados por un espacio en blanco.

Salida

Para cada caso de prueba, el programa debe imprimir una sola línea, que contiene un número entero, que indica el número de veces que el láser tiene que estar encendido para esculpir el bloque en el formato indicado.

Ejemplo de entrada Ejemplo de salida

5 8
1 2 3 2 0 3 4 5
3 3
1 0 2
4 3
4 4 1
0 0

7
3
3