Maximize Additional Seating

This problem involves determining the maximum number of additional people that can be seated in a row of n seats while maintaining a required social distancing rule. Specifically, there must be at least one empty seat between any two people. Some of the seats are already occupied, and the occupied positions are provided. Your task is to calculate the maximum number of additional people that may be seated without violating the distancing rule.

Note: The positions of the seats are numbered from 1 to n. If no seat is initially occupied, people can only be seated in alternate seats.

The calculation for additional seating in any gap of empty seats between two occupied seats can be described by the formula: $$\left\lfloor \frac{gap - 1}{2} \right\rfloor$$ where gap is the number of consecutive empty seats between two occupied seats. The same idea applies to the gaps before the first occupied seat and after the last occupied seat.

inputFormat

The input is read from standard input (stdin) and is structured as follows:

• The first line contains two integers n and m, representing the total number of seats and the number of already occupied seats, respectively.
• If m > 0, the second line contains m distinct integers indicating the positions of the occupied seats.

outputFormat

Output a single integer to standard output (stdout) — the maximum number of additional people that can be seated without violating the social distancing rule.

10 2
2 6

3