Question
Shortest Circular Route
Liam has been assigned to check on N maintenance points located around a circular track with a total length of K meters. Each point is positioned at a certain distance, Di, from the starting line on the northern edge of the track. Liam can begin his inspection from any point and needs to visit each one, but he wants to travel the shortest distance possible to complete his rounds. Since he can only move in a circular path along the track, what is the minimum distance Liam must travel to visit all the maintenance points?
Input
The first line of the input contains two integers K and N.
The second line of the input contains N space-separated integers, D0, D1, … Dn-1 representing the distance of all the houses from the northmost point
Constraints
2 ≤ k ≤ 106
2 ≤ N ≤ 2 × 10^5
0 ≤ Di <. . < Dn < k
The second line of the input contains N space-separated integers, D0, D1, … Dn-1 representing the distance of all the houses from the northmost point
Constraints
2 ≤ k ≤ 106
2 ≤ N ≤ 2 × 10^5
0 ≤ Di <. . < Dn < k
Output
Find the minimum distance Liam must travel to visit all the maintenance points
Example
Sample Input
20 3
5 10 15
Sample Output
10
Sample Input
20 3
0 5 15
Sample Output
10
20 3
5 10 15
Sample Output
10
Sample Input
20 3
0 5 15
Sample Output
10