Social Distancing

문제

It's time for a social distancing party! A group of friends are sitting around a circular table where some seats are filled and some seats are empty. In particular, to maintain social distancing protocols, no two people are sitting directly beside each other.

They want to expand the party and include more friends, but no one is willing to move out of their current seat. Given the current table seating, determine the maximum number of additional people that can be seated such that there is still at least one empty seat between all pairs of people seated.

입력

The first line of input contains two integers $SS$ ($3\le S\le 10003\; \backslash leq\; S\; \backslash leq\; 1\backslash ,000$), which is the number of seats at the table, and $NN$ ($1\le N\le S\mathrm{/}21\; \backslash leq\; N\; \backslash leq\; S/2$), which is the number of people that are already seated at the table.

Note that the seats of the table are numbered $1,2,\dots ,S1,\; 2,\; \backslash ldots,\; S$ in a circular fashion: for each , seats numbered $ii$ and $i+1i+1$ are directly beside each other. Seats $SS$ and $11$ are also directly beside each other.

The second line contains $NN$ integers $a_1,a_2,\dots ,a_{N}a\_1,\; a\_2,\; \backslash ldots,\; a\_N$ (), which indicates that seat number $a_{i}a\_\{i\}$ is currently occupied. No two occupied seats are directly beside each other.

출력

Display the maximum number of additional friends that can be seated at the table such that there is still at least one empty seat between all pairs of people seated.