Laser Sculpting

Time limit2sMemory limit512 MB

Summary

Given a block's height profile, count the number of horizontal 1 mm laser sweeps needed to carve it into the target shape.

Level: Medium5 of 10
Topics: Simulation, Implementation, Greedy
Solved: No attempts yet

Problem

Since the laser was invented in 1958, it has been used in a huge variety of applications, among them electronic equipment, surgical instruments, and weapons.

The figure above is a schematic diagram of a machine that sculpts a solid block of material with a laser. The machine has a laser emitter that travels horizontally to the right and to the left at constant speed. When the emitter is switched on while it travels, a layer of constant thickness is vaporised and removed from the block along the stretch where the laser was on.

The figure below illustrates the sculpting process. Part (a) is a block 5 mm high and 8 mm long at the start of the process, part (b) is the shape the sculpted block has to end up with, and part (c) is the order in which the layers come off, assuming that each sweep removes a layer 1 mm thick. The first sweep removes the piece numbered 1, the second sweep removes the piece numbered 2, and so on. During the process the laser was switched on 7 times in total, once for each piece removed.

Write a program that reads the height of the block, the length of the block, and the final shape the block has to end up with, then determines how many times in total the laser has to be switched on.

Input

The input contains several test cases. Each test case has two lines.

The first line has the height $A$ and the length $C$ of the block to be sculpted, separated by a single space. Both are in millimetres ( $1 \le A \le 10^4$ , $1 \le C \le 10^4$ ).

The second line has $C$ integers $X_0, X_1, \dots, X_{C-1}$ separated by spaces. The value $X_i$ is the final height of the block, in millimetres, over the stretch between position $i$ and position $i+1$ along the length ( $0 \le X_i \le A$ ).

Along the stretch where the laser is on, every sweep removes a layer 1 millimetre thick from the block.

The last line of the input has only two zeros, separated by a single space.

Output

For each test case print a single line with one integer, the number of times the laser has to be switched on to sculpt the block into the given shape.

Examples6

Example 1

Input

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

Expected output

7
3
3

Example 2
Input
```
3 4
3 3 3 3
0 0
```
Expected output
```
0
```
Example 3
Input
```
5 4
0 0 0 0
0 0
```
Expected output
```
5
```
Example 4
Input
```
2 5
0 2 0 2 0
0 0
```
Expected output
```
6
```
Example 5
Input
```
1 1
0
1 1
1
0 0
```
Expected output
```
1
0
```

Example 6

Input

6 6
6 5 4 3 2 1
6 6
1 2 3 4 5 6
0 0

Expected output

5
5