Laps

Interview

Time limit1sMemory limit512 MB

Summary

Given per-minute track positions from a monotone run on an n-metre loop, find the smallest possible total forward distance modulo n in laps.

Level: Medium4 of 10
Topics: Array, Math, Greedy, Implementation
Solved: No attempts yet

Problem

Bethany is training for an athletics contest. Yesterday, she ran laps around an oval athletics track. She recorded her location on the track every minute. She has now forgotten how many laps she did yesterday. Bethany has given you this list of locations on the track. Each location is the number of metres Bethany has run since the last time she passed the start point. Bethany always starts at the start point. Note that it is possible that Bethany does not move between two entries in the list. However, she will never run backwards. The athletics track is n metres long. This means that if Bethany ran n metres in total she would return to the start point.

Suppose you have a 300 metre long track and Bethany ran 200 metres from the start point. Bethany would record 200. Then, if she ran another 200 metres, she would record 100 having crossed the start point.

She wants to determine the minimum number of laps she could have completed. Can you help?

Input

The first line of input contains two integers n (1 ≤ n ≤ 10^9) and m (1 ≤ m ≤ 10^5), the length of the track and the number of locations Bethany recorded in her list. The next line contains m integers each of which is at least 0 and at most n − 1. These are the list of locations Bethany recorded. The list is in increasing order of time.

Output

Display the minimum number of laps Bethany could have completed.

Examples4

Example 1
Input
```
1 1
0
```
Expected output
```
0
```
Example 2
Input
```
4 2
2 1
```
Expected output
```
1
```
Example 3
Input
```
5 4
2 1 4 1
```
Expected output
```
2
```
Example 4
Input
```
3 7
0 1 2 0 1 2 0
```
Expected output
```
2
```