const int NMax=1100;
inline int MIN(int a,int b)
{
    return (a<b)?a:b;
}
struct node
{
    int key,dist;
    node *left,*right;
}*S[NMax],pool[NMax];
int N,K,A[NMax],A1[NMax];
void make(node *a,int K)
{
    a->key=K;
    a->dist=0;
    a->left=a->right=NULL;
}
node* merge(node *a,node *b)
{
    if(a==NULL) return b;
    if(b==NULL) return a;
    if(a->key<b->key) swap(a,b);
    a->right=merge(a->right,b);
    if(a->left==NULL || a->right->dist>a->left->dist)
        swap(a->right,a->left);
    if(a->right==NULL) a->dist=0;
    else a->dist=a->right->dist+1;
    return a;
}
int L,W[NMax],NUM[NMax],Cnt[NMax],TCnt[NMax],Non[NMax],TNon[NMax],La[NMax],F1[NMax][NMax],F2[NMax][NMax],dp[NMax];
int main()
{
    while(scanf("%d%d",&N,&K),N)
    {
        for(int i=1;i<=N;i++) dp[i]=100000000;
    for(int i=1;i<=N;i++)
        scanf("%d",A1+i);
    for(int i=1;i<=N;i++)
        A[i]=A1[i]-i;
for(int I=1;I<N;I++)
{
    L=1,S[1]=&pool[I];
    make(S[1],A[I]);
    W[1]=A[I],NUM[1]=1,Cnt[1]=1,TCnt[1]=A[I],TNon[1]=0,Non[1]=0,La[1]=0;
    for(int i=I+1;i<=N;i++)
    {
        L++;
        S[L]=&pool[i];
        make(S[L],A[i]);
        W[L]=A[i],NUM[L]=1,Cnt[L]=1,TCnt[L]=A[i],TNon[L]=0,Non[L]=0,La[L]=0;
        while(L>1 && W[L]<W[L-1])
        {
            node *tmp=merge(S[L],S[L-1]);
            Cnt[L-1]+=Cnt[L],TCnt[L-1]+=TCnt[L],TNon[L-1]+=TNon[L],Non[L-1]+=Non[L];
            if((NUM[L]+1)/2+(NUM[L-1]+1)/2>(NUM[L]+NUM[L-1]+1)/2)
            {
                int tmp1=tmp->key;
                tmp=merge(tmp->left,tmp->right);
                Cnt[L-1]--,TCnt[L-1]-=tmp1;
                Non[L-1]++,TNon[L-1]+=tmp1;
            }
            NUM[L-1]=NUM[L]+NUM[L-1];
            S[L-1]=tmp;
            W[L-1]=tmp->key;
            L--;
        }
        F1[I][i]=La[L]=La[L-1]+(W[L]*Cnt[L]-TCnt[L]+TNon[L]-Non[L]*W[L]);
    }
}
for(int i=1;i<=N;i++)
        A[i]=-(A1[i]+i);
for(int I=1;I<N;I++)
{
    L=1,S[1]=&pool[I];
    make(S[1],A[I]);
    W[1]=A[I],NUM[1]=1,Cnt[1]=1,TCnt[1]=A[I],TNon[1]=0,Non[1]=0,La[1]=0;
    for(int i=I+1;i<=N;i++)
    {
        L++;
        S[L]=&pool[i];
        make(S[L],A[i]);
        W[L]=A[i],NUM[L]=1,Cnt[L]=1,TCnt[L]=A[i],TNon[L]=0,Non[L]=0,La[L]=0;
        while(L>1 && W[L]<W[L-1])
        {
            node *tmp=merge(S[L],S[L-1]);
            Cnt[L-1]+=Cnt[L],TCnt[L-1]+=TCnt[L],TNon[L-1]+=TNon[L],Non[L-1]+=Non[L];
            if((NUM[L]+1)/2+(NUM[L-1]+1)/2>(NUM[L]+NUM[L-1]+1)/2)
            {
                int tmp1=tmp->key;
                tmp=merge(tmp->left,tmp->right);
                Cnt[L-1]--,TCnt[L-1]-=tmp1;
                Non[L-1]++,TNon[L-1]+=tmp1;
            }
            NUM[L-1]=NUM[L]+NUM[L-1];
            S[L-1]=tmp;
            W[L-1]=tmp->key;
            L--;
        }
        F2[I][i]=La[L]=La[L-1]+(W[L]*Cnt[L]-TCnt[L]+TNon[L]-Non[L]*W[L]);
    }
}
    for(int i=1;i<=K;i++)
    {
        dp[0]=0;
        for(int j=N;j>=1;j--)
        {
            for(int k=0;k<j;k++)
                dp[j]=MIN(dp[j],dp[k]+MIN(F1[k+1][j],F2[k+1][j]));
        }
    }
    printf("%d\n",dp[N]);
    }
    return 0;
}