#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,int>
#define X first
#define Y second
const int N=1e5+5;
const int oo=1e9+1;
int n,k;
int a[N];
namespace sub1
{
int limit,res;
bool check[N];
void ql(int i,int used,int sum,bool onFire)
{
if (i>limit)
{
res=min(res,sum);
return;
}
if (!check[i]) ql(i+1,used,sum,0);
if (used+(onFire==false)<=k) ql(i+1,used+(onFire==false),sum+1,1);
}
void solve()
{
limit=a[n];
for (int i=1;i<=n;i++)
check[a[i]]=true;
res=oo;
ql(1,0,0,0);
cout << res;
}
}
namespace sub2
{
int dp_before[N],dp_cur[N];
void dnc(int l,int r,int optl,int optr)
{
if (l>r) return;
int mid=(l+r)/2;
int limit=min(optr,mid);
pii best=make_pair(oo,0);
for (int i=optl;i<=limit;i++)
best=min(best,make_pair((ll)dp_before[i-1]+a[mid]-a[i]+1,-i));
dp_cur[mid]=best.X;
int opt=-best.Y;
dnc(l,mid-1,optl,opt);
dnc(mid+1,r,opt,optr);
}
void solve()
{
for (int i=1;i<=n;i++)
dp_before[i]=a[i]-a[1]+1;
for (int j=2;j<=k;j++)
{
dnc(1,n,1,n);
for (int i=1;i<=n;i++)
dp_before[i]=dp_cur[i];
}
cout << dp_before[n];
}
}
namespace sub3
{
pii cmp_pair(pii x,pii y)
{
if (x.X==y.X) return max(x,y);
return min(x,y);
}
ll l,r,mid,res;
pii dp[N];
pii check(int lambda)
{
dp[1]=make_pair(1+lambda,1);
for (int i=2;i<=n;i++)
dp[i]=cmp_pair(make_pair(dp[i-1].X+a[i]-a[i-1],dp[i-1].Y),make_pair(dp[i-1].X+1+lambda,dp[i-1].Y+1));
return dp[n];
}
void solve()
{
res=0;
l=0;
r=1e9;
while (l<=r)
{
mid=(l+r)/2;
if (check(mid).Y>=k)
{
l=mid+1;
res=mid;
}
else r=mid-1;
}
cout << check(res).X-res*k;
}
}
int main()
{
ios_base::sync_with_stdio(NULL);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> k;
for (int i=1;i<=n;i++)
cin >> a[i];
sub3::solve();
}
