#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define vi vector<long long>
#define all(x) x.begin(), x.end()
#define endl "\n"
void solution();
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solution();
return 0;
}
const int N = 1e5+10;
ll a[N];
ll cost(int i, int j) {
return a[j]+1 - a[i];
}
vi dp;
void dnc(int l, int r, int optl, int optr, vi &ndp) {
if (l > r) return;
int mid = (l + r)/2;
int best = mid;
for (int i = optl; i <= min(mid, optr); i++) {
if (ndp[mid] > dp[i-1] + cost(i, mid)) {
best = i;
ndp[mid] = dp[i-1] + cost(i, mid);
}
}
dnc(l, mid-1, optl, best, ndp);
dnc(mid+1, r, best, optr, ndp);
}
void solution() {
ll n, k; cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
dp.resize(n+1, 1e18);
dp[0] = 0;
for (int i = 1; i <= k; i++) {
vi ndp(n+1, 1e18);
dnc(1, n, 1, n, ndp);
dp = move(ndp);
}
cout << dp[n] << endl;
}
