Mario

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:

• All lockers are disposed in a line and numerated with positive integers starting from 1. This allows Mario to save time when looking for a locker;
• All lockers have wheels, this gives him a lot of flexibility when rearranging his lockers (naturally, when Mario switches two lockers' positions, he also changes their numeration, so that they continue to be sequentially numerated starting from number 1).

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.