arrange

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <iostream>
#include <cstdio>
#define task ""
using namespace std;
using ll = long long;
using ld = long double;

const int N = 2e3 + 2;
int n;
const ll Inf = 1e17;
ll m, dp[N][N];
ll pre[N][N];
ll suf[N][N];
ll a[N];

void Read(){
    cin >> m >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i],
        a[i] += a[i - 1];

}

inline ll f(int i, int j){
    return a[i] - a[j - 1] + i - j;
}

void Solve(){
    fill_n(&dp[0][0], N * N, Inf);
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= i; ++j)
            if(f(i, j) <= m){
                if(j == 1) dp[i][j] = 0;
                else{
                    int low = 1, mid, high = j - 1;
                    while(low <= high){
                        mid = (low + high) / 2;
                        if(f(j - 1, mid) <= f(i, j)) high = mid - 1;
                        else low = mid + 1;
                    }
                    if(high > 0)
                        dp[i][j] = pre[j - 1][high] - f(i, j);
                    if(low < j)
                        dp[i][j] = min(dp[i][j], suf[j - 1][low] + f(i, j));
                }
            }
        pre[i][0] = suf[i][i + 1] = Inf;
        for(int j = 1; j <= i; ++j)
            pre[i][j] = min(pre[i][j - 1], dp[i][j] + f(i, j));
        for(int j = i; j; --j)
            suf[i][j] = min(suf[i][j + 1], dp[i][j] - f(i, j));
    }
    ll ans = Inf;
    for(int i = 1; i <= n; ++i)
        ans = min(ans, dp[n][i]);
    cout << ans;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".INP", "r")){
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }
    Read();
    Solve();
}