#include <bits/stdc++.h>
#include <iostream>
#include <queue>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)

#define sz(x) (long long)(x).size()

int dp[1001][2][100001];
int b, p;

// int func(int onBob, int idx, int a) {
//     if (idx >= 1000) {
//         return max(a, dp[onBob][idx][a]);
//     }
// }

int main() {
    cin >> b >> p;
    vector<int> A(p), B(p);
    rep(i, p) {
        cin >> A[i];
        B[i] = b-A[i]-1;
        if (i==p-1) B[i]++;
    }
    reverse(A.begin(), A.end());
    reverse(B.begin(), B.end());
    rep(i, 1001) rep(k, 2) rep(j, 100001) dp[i][k][j] = 1e9;
    dp[0][0][0] = 0;
    dp[0][1][0] = 0;
    rep(idx, p) {
        rep(onBob, 2) {
            rep(alice, 100001) {
                if (dp[idx][onBob][alice]==1e9) continue;
                
                if (onBob==0){
                    dp[idx+1][0][A[idx]+alice] = min(dp[idx+1][0][A[idx]+alice], dp[idx][onBob][alice]);
                    dp[idx+1][1][A[idx]+alice] = min(dp[idx+1][1][A[idx]+alice], dp[idx][onBob][alice]+1);
                }
                if (onBob==1){
                    dp[idx+1][0][alice+1] = min(dp[idx+1][0][alice+1], dp[idx][onBob][alice]+B[idx]);
                    dp[idx+1][1][alice] = min(dp[idx+1][1][alice], dp[idx][onBob][alice]+B[idx]);
                }
            }
        }
    }
    int mn = 1e9;
    rep(onBob, 2) {
        rep(alice, 100001) {
            if (dp[p][onBob][alice]==1e9) continue;
            mn = min(mn, max(dp[p][onBob][alice], alice));
            // cout << onBob << ' ' << alice << endl;
            // cout << dp[p][onBob][alice] << endl;
        }
    }
    cout << mn << endl;
}