랩 수

면접 대비

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

요약

n미터 트랙에서 한 방향으로 달리며 매분 기록한 위치 목록이 주어질 때 최소 랩 수를 구한다.

난이도: 보통10점 중 4점
유형: 배열, 수학, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

Bethany는 육상 대회를 준비하고 있다. 어제 그녀는 타원형 트랙을 돌며 달렸다. 그녀는 1분마다 트랙 위에서의 자신의 위치를 기록했다. 이제 그녀는 어제 몇 바퀴를 돌았는지 기억하지 못한다. Bethany가 너에게 이 위치 목록을 주었다. 각 위치는 Bethany가 마지막으로 출발점을 지난 이후 달린 거리(미터)이다. Bethany는 항상 출발점에서 시작한다. Bethany가 목록의 두 항목 사이에서 움직이지 않을 수도 있다. 그러나 그녀는 절대 뒤로 달리지 않는다. 트랙의 길이는 n미터이다. 즉, Bethany가 총 n미터를 달리면 출발점으로 돌아온다.

길이가 300미터인 트랙에서 Bethany가 출발점으로부터 200미터를 달렸다고 하자. Bethany는 200을 기록했을 것이다. 그런 다음 그녀가 200미터를 더 달리면 출발점을 지나 100을 기록했을 것이다.

그녀는 자신이 완주했을 수 있는 최소 바퀴 수를 알고 싶어 한다. 도와줄 수 있는가?

입력

입력의 첫 번째 줄에는 두 정수 n (1 ≤ n ≤ 10^9)과 m (1 ≤ m ≤ 10^5)이 주어진다. 이는 트랙의 길이와 Bethany가 목록에 기록한 위치의 개수이다. 다음 줄에는 m개의 정수가 주어지며, 각 값은 0 이상 n − 1 이하이다. 이것이 Bethany가 기록한 위치 목록이다. 목록은 시간 순으로 정렬되어 있다.

출력

Bethany가 완주했을 수 있는 최소 바퀴 수를 출력한다.

예제4

예제 1
입력
```
1 1
0
```
예상 출력
```
0
```
예제 2
입력
```
4 2
2 1
```
예상 출력
```
1
```
예제 3
입력
```
5 4
2 1 4 1
```
예상 출력
```
2
```
예제 4
입력
```
3 7
0 1 2 0 1 2 0
```
예상 출력
```
2
```