#include <bits/stdc++.h>

using namespace std;
using ld = long double;

int b, p;

vector<int> al, bb;

bool check(int mx) {
    int c1 = 0, c2 = 0;
    vector<int> a1 = al, a2 = bb;
    a1.push_back(0);
    a2.push_back(0);
    for (int i = 0; i < al.size(); ++i) {
        if (a1[i] < a2[i]) {
            if (c1 + a1[i] <= mx) {
                c1 += a1[i];
                int j = i;
                a2[i] += a1[i];
                while (a2[j] == b) {
                    a2[j++] = 0;
                    a2[j]++;
                }
            } else if (c2 + a2[i] <= mx) {
                c2 += a2[i];
                int j = i;
                a1[i] += a2[i];
                while (a1[j] == b) {
                    a1[j++] = 0;
                    a1[j]++;
                }
            } else return false;
        } else {
            if (c2 + a2[i] <= mx) {
                c2 += a2[i];
                int j = i;
                a1[i] += a2[i];
                while (a1[j] == b) {
                    a1[j++] = 0;
                    a1[j]++;
                }
            } else if (c1 + a1[i] <= mx) {
                c1 += a1[i];
                int j = i;
                a2[i] += a1[i];
                while (a2[j] == b) {
                    a2[j++] = 0;
                    a2[j]++;
                }
            } else return false;
        }
    }
    return c1 <= mx and c2 <= mx;
}

void test_case() {
    cin >> b >> p;
    al.resize(p);
    bb.resize(p);
    for (int &x : al)
        cin >> x;
    reverse(al.begin(), al.end());
    bb[0] = b - al[0];
    for (int i = 1; i < p; ++i)
        bb[i] = b - al[i] - 1;
    int l = 0, r = 1e9;
    while (l <= r) {
        int m = (l + r) / 2;
        if (check(m))
            r = m - 1;
        else l = m + 1;
    }
    cout << l << '\n';
}

signed main() {
    ios::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr);
    test_case();
    // int tc; cin >> tc;
    // while (tc--) {
    //     test_case();
    // }
    return 0;
}