//   ██   █    █            ▄▄▄▄▀ ▄  █ ████▄    ▄▄▄▄▄   ▄███▄       █▀▄▀█ ████▄ █▀▄▀█ ▄███▄      ▄     ▄▄▄▄▀ ▄▄▄▄▄          
//   █ █  █    █         ▀▀▀ █   █   █ █   █   █     ▀▄ █▀   ▀      █ █ █ █   █ █ █ █ █▀   ▀      █ ▀▀▀ █   █     ▀▄        
//   █▄▄█ █    █             █   ██▀▀█ █   █ ▄  ▀▀▀▀▄   ██▄▄        █ ▄ █ █   █ █ ▄ █ ██▄▄    ██   █    █ ▄  ▀▀▀▀▄          
//   █  █ ███▄ ███▄         █    █   █ ▀████  ▀▄▄▄▄▀    █▄   ▄▀     █   █ ▀████ █   █ █▄   ▄▀ █ █  █   █   ▀▄▄▄▄▀           
//      █     ▀    ▀       ▀        █                   ▀███▀          █           █  ▀███▀   █  █ █  ▀                     
//     █                           ▀                                  ▀           ▀           █   ██                        
//    ▀                                                                                                                     
//     ▄ ▄   ▄█ █    █         ███   ▄███▄       █    ████▄    ▄▄▄▄▄      ▄▄▄▄▀     ▄█    ▄          ▄▄▄▄▀ ▄█ █▀▄▀█ ▄███▄   
//    █   █  ██ █    █         █  █  █▀   ▀      █    █   █   █     ▀▄ ▀▀▀ █        ██     █      ▀▀▀ █    ██ █ █ █ █▀   ▀  
//   █ ▄   █ ██ █    █         █ ▀ ▄ ██▄▄        █    █   █ ▄  ▀▀▀▀▄       █        ██ ██   █         █    ██ █ ▄ █ ██▄▄    
//   █  █  █ ▐█ ███▄ ███▄      █  ▄▀ █▄   ▄▀     ███▄ ▀████  ▀▄▄▄▄▀       █         ▐█ █ █  █        █     ▐█ █   █ █▄   ▄▀ 
//    █ █ █   ▐     ▀    ▀     ███   ▀███▀           ▀                   ▀           ▐ █  █ █       ▀       ▐    █  ▀███▀   
//     ▀ ▀                                                                             █   ██                   ▀           
                                                                                                                       
//   █    ▄█ █  █▀ ▄███▄          ▄▄▄▄▀ ▄███▄   ██   █▄▄▄▄   ▄▄▄▄▄       ▄█    ▄       █▄▄▄▄ ██   ▄█    ▄                   
//   █    ██ █▄█   █▀   ▀      ▀▀▀ █    █▀   ▀  █ █  █  ▄▀  █     ▀▄     ██     █      █  ▄▀ █ █  ██     █                  
//   █    ██ █▀▄   ██▄▄            █    ██▄▄    █▄▄█ █▀▀▌ ▄  ▀▀▀▀▄       ██ ██   █     █▀▀▌  █▄▄█ ██ ██   █                 
//   ███▄ ▐█ █  █  █▄   ▄▀        █     █▄   ▄▀ █  █ █  █  ▀▄▄▄▄▀        ▐█ █ █  █     █  █  █  █ ▐█ █ █  █                 
//       ▀ ▐   █   ▀███▀         ▀      ▀███▀      █   █                  ▐ █  █ █       █      █  ▐ █  █ █ ██              
//            ▀                                   █   ▀                     █   ██      ▀      █     █   ██                 
//                                               ▀                                            ▀                             
//      ▄▄▄▄▀ ▄█ █▀▄▀█ ▄███▄          ▄▄▄▄▀ ████▄     ██▄   ▄█ ▄███▄                                                        
//   ▀▀▀ █    ██ █ █ █ █▀   ▀      ▀▀▀ █    █   █     █  █  ██ █▀   ▀                                                       
//       █    ██ █ ▄ █ ██▄▄            █    █   █     █   █ ██ ██▄▄                                                         
//      █     ▐█ █   █ █▄   ▄▀        █     ▀████     █  █  ▐█ █▄   ▄▀                                                      
//     ▀       ▐    █  ▀███▀         ▀                ███▀   ▐ ▀███▀ ██                                                     
//                 ▀                                                                                                        
                                                                                                                       


// GOD
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// Brewing spells
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

// Magics
#define ea ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fili freopen("input", "r", stdin);
#define filo freopen("output", "w", stdout);
#define dbg(var) cout<<#var<<"=>"<<var<<endl;
#define rep(i, a, n) for(ll i = a; i < n; i++)
#define reprev(i, a, n) for(ll i = a; i > n; i--)
#define endl "\n"
#define MOD 1000000007
#define len(x) ((int)(x).size())
#define F first
#define S second
#define PB push_back
#define tuple(type, size) array<type, size>
#define exist(DS, el) ((DS.find(el) != DS.end()))
#define elif else if

// Dark Magics
#define HashMap unordered_map
#define HashSet unordered_set
#define TreeMap map
#define TreeSet set
#define MultiTreeSet multiset
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // order_of_key, find_by_order
// typedef unordered_map<long long, int, custom_hash> safe_map; // simple hash map
// typedef gp_hash_table<long long, int, custom_hash> safe_hash_table; // faster hash map



typedef struct FenwickTree {
	vector<int> bit;
	int n;

	FenwickTree(int n) {
		this->n = n+1;
		bit.assign(n+1, 0);
	}

	FenwickTree(vector<int> &a): FenwickTree(a.size()) {
		for(size_t i = 0; i < a.size(); i++) {
			upd(i, a[i]);
		}
	}

	int sum(int idx) {
		idx++;
		int ret = 0;
		while (idx > 0) {
			ret += bit[idx];
			idx -= (idx&-idx);
		}
		return ret;
	}

	int sum(int l, int r) {
		return sum(r) - sum(l-1);
	}

	void upd(int idx, int delta) {
		idx++;
		while (idx <= n) {
			bit[idx] += delta;
			idx += (idx&-idx);
		}
	}
} BIT;



// My puny solution
int main() {
    // Selemat pagi
    ea 
    // fili filo
    // Selemat tingal

    int T;
    // cin >> T;
    T = 1;
    while (T--) {
  
    	int k, n;
    	cin >> k >> n;
    	int arr[n];
    	ll tot = 0;
    	rep(i, 0, n) cin >> arr[i];

    	pii left = {arr[0] + k - arr[n-1], 0};
    	pii right = {arr[1] - arr[0], 0};

    	rep(i, 0, n-1) {
    		pii sel = min(left, right);
    		tot += sel.F;
    		int ind = sel.S;
    		if (sel == left) {
    			if (ind == 0) ind = n-1;
    			else ind = ind-1;
    			left = {arr[ind] - arr[ind-1], ind};
    		}
    		else {
    			ind++;
    			right = {arr[ind+1] - arr[ind], ind};
    		}
    	}

    	cout << tot << endl;
    }
}



Measured memory_bytes: 1024