Social Distancing

Interview

Time limit1sMemory limit1024 MB

Summary

Given S circular seats with N occupied, find how many more people can sit so that no two seated people are adjacent.

Level: Easy3 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

It is time for a social distancing party! A group of friends are sitting around a circular table. Some seats are filled and some are empty. To follow the distancing rules, no two people sit directly beside each other.

The friends want to expand the party and invite more people, but no one is willing to move from their current seat. Given the current seating, find the maximum number of additional people who can be seated so that every pair of seated people still has at least one empty seat between them.

Input

The first line contains two integers $S$ ( $3 \leq S \leq 1\,000$ ) and $N$ ( $1 \leq N \leq S/2$ ). $S$ is the number of seats at the table, and $N$ is the number of people already seated.

The seats are numbered $1, 2, \ldots, S$ in a circle. For each $1 \leq i < S$ , seats $i$ and $i+1$ are directly beside each other. Seats $S$ and $1$ are also directly beside each other.

The second line contains $N$ integers $a_1, a_2, \ldots, a_N$ ( $1 \leq a_1 < a_2 < \cdots < a_N \leq S$ ), meaning seat $a_i$ is already occupied. No two occupied seats are directly beside each other.

Output

Print the maximum number of additional people who can be seated at the table so that there is still at least one empty seat between every pair of seated people.

Examples5

Example 1
Input
```
9 2
2 6
```
Expected output
```
2
```
Example 2
Input
```
10 3
1 4 7
```
Expected output
```
1
```
Example 3
Input
```
6 2
2 5
```
Expected output
```
0
```
Example 4
Input
```
100 5
7 14 47 78 99
```
Expected output
```
43
```
Example 5
Input
```
6 1
3
```
Expected output
```
2
```