소셜 디스턴싱

면접 대비

시간 제한1초메모리 제한1024 MB

요약

원형 테이블의 S개 좌석 중 N개가 찹니다. 앉은 모든 사람 사이에 빈 좌석이 하나 이상 있도록 더 앉힐 수 있는 최대 인원을 구합니다.

난이도: 쉬움10점 중 3점
유형: 수학, 구현
정답자: 아직 제출이 없습니다

문제

소셜 디스턴싱 파티를 열 시간이다. 친구 몇 명이 원형 테이블에 둘러앉아 있다. 일부 자리는 채워져 있고 일부는 비어 있다. 방역 지침을 지키기 위해 바로 옆에 앉은 두 사람은 없다.

친구들은 파티를 넓혀 더 많은 사람을 부르고 싶지만, 아무도 지금 앉은 자리에서 옮기려 하지 않는다. 현재 자리 배치가 주어졌을 때, 앉은 사람들 사이에 빈 자리가 최소 하나씩 남도록 추가로 앉힐 수 있는 최대 인원 수를 구하라.

입력

첫 줄에는 두 정수 $S$ ( $3 \leq S \leq 1\,000$ )와 $N$ ( $1 \leq N \leq S/2$ )이 주어진다. $S$ 는 테이블의 자리 수이고, $N$ 은 이미 앉아 있는 사람의 수이다.

자리는 원형으로 $1, 2, \ldots, S$ 번 번호가 매겨져 있다. $1 \leq i < S$ 인 각 $i$ 에 대해 자리 $i$ 와 $i+1$ 은 서로 바로 옆이다. 자리 $S$ 와 $1$ 도 서로 바로 옆이다.

둘째 줄에는 $N$ 개의 정수 $a_1, a_2, \ldots, a_N$ ( $1 \leq a_1 < a_2 < \cdots < a_N \leq S$ )이 주어진다. 이는 자리 $a_i$ 가 이미 차 있다는 뜻이다. 차 있는 두 자리가 서로 바로 옆에 있는 경우는 없다.

출력

앉은 사람들 사이에 빈 자리가 적어도 하나 있도록 테이블에 추가로 앉힐 수 있는 최대 인원 수를 출력한다.

예제5

예제 1
입력
```
9 2
2 6
```
예상 출력
```
2
```
예제 2
입력
```
10 3
1 4 7
```
예상 출력
```
1
```
예제 3
입력
```
6 2
2 5
```
예상 출력
```
0
```
예제 4
입력
```
100 5
7 14 47 78 99
```
예상 출력
```
43
```
예제 5
입력
```
6 1
3
```
예상 출력
```
2
```