#include <stdio.h>
#define MAXN 100005
#define MAXK 202
typedef long long lld;
int N,K,A[MAXN],S[MAXN],P[MAXN][MAXK];
double pos[MAXN]; int stk[MAXN],scnt;
lld D[MAXN],E[MAXN];
double get_cross(int a,int b){ return -double(D[a]-S[a]*S[a]-D[b]+S[b]*S[b])/(S[a]-S[b]); }
int main()
{
int i,j,k;
scanf("%d%d",&N,&K); ++K;
for (i=1;i<=N;i++) scanf("%d",A+i), S[i] = S[i-1]+A[i];
stk[++scnt] = 0; pos[scnt] = -1e9;
for (j=1;j<=K;j++){
int p = 1;
for (i=j;i<=N;i++){
while (p < scnt && stk[p+1] < i && pos[p+1] <= S[i]) p++;
int t = stk[p];
D[i] = E[t]+(lld)(S[i]-S[t])*S[t]; P[i][j] = t;
//printf("D[%d][%d]: %d, P[%d][%d]: %d\n",i,j,D[i],i,j,t);
}
scnt = 0; stk[++scnt] = j; pos[scnt] = -1e9;
for (i=j+1;i<=N;i++) if (S[i]){
while (scnt > 1 && get_cross(stk[scnt],i) <= pos[scnt]) scnt--;
stk[++scnt] = i; pos[scnt] = get_cross(stk[scnt-1],i);
}
for (i=1;i<=N;i++) E[i] = D[i];
}
printf("%lld\n",D[N]);
for (i=N,j=K;j;){
if (i < N) printf("%d ",i);
i = P[i][j--];
} puts("");
}
