beecrowd | 1408


By Fábio Dias Moreira Brazil
Timelimit: 3

Mario is the owner of a locker company, the Moderate Cost Lockers (MCL). Mario won his clients thanks to the quickness of the process of storing volumes. He has two techniques for this:

To rent lockers to a new client, Mario likes to use adjacent lockers, after all, at the beginning of the rental a new client normally makes a lot of requisitions to access the content stored, and the fact that the lockers are adjacent helps when accessing it, both to Mario and to the client.

If Mario has free lockers and in sufficient quantity, he can always make that. For example, if the requisition of a new client needs 4 lockers but only the lockers of numbers 1, 3, 5, 6 and 8 are available, Mario can switch the positions of the lockers 5 and 2 and of the lockers 6 and 4, so that he can rent the interval of lockers from 1 to 4.

However, to minimize the service time, Mario wants to do the smallest number of switches as possible to store each volume. On the example above, he could simply switch the lockers 1 and 4, and rent the interval from 3 to 6.

Mario is really busy with his clients and asked you to make a program to determine the smallest number of switches necessary to satisfy a new client's request.


The input contains several test cases. The first line of a test case contains two integers N and L (1 ≤ NL ≤ 100000), indicating how many lockers are necessary to satisfy the new client's request and how many lockers are available, respectively. The following line contains L positive integers separated by blank spaces, none bigger than 1000000000, indicating the positions of the available lockers. The numbers of the free lockers are given in ascending order.

The end of the input is indicated by N = L = 0.


For each test case, print one line containing only one integer number, indicating the minimum number of switches that Mario has to do to satisfy the new client's request (that is, have N adjacent lockers available).

Sample Input Sample Output

5 6
1 3 4 5 6 8
5 5
1 3 5 6 8
5 6
1 4 5 6 7 8
0 0