#include <stdio.h>
#include <string.h>
#define bad(x,y,z) ((C[y]-C[x])*(M[x]-M[z]) >= (C[z]-C[x])*(M[x]-M[y]))
int a[100005];
long long dpnew[100005];
long long dpold[100005]; // End with i, having j parts;
long long qs[100005];
int par[100005][256];
int M[100005];
long long C[100005];
int idx[100005];
int prt[100005];
int fastscan(){
int x = 0;
int c = getchar();
while(c < 48 || c >= 58) c = getchar();
while(c >= 48 && c < 58){
x *= 10;
x += c-48;
c = getchar();
}
return x;
}
int csz;
int main(){
int ptr;
int n,k;
n = fastscan();
k = fastscan();
k++;
csz++;
for(int i = 1; i <= n; i++){
a[i] = fastscan();
qs[i] = qs[i-1] + (long long)a[i];
dpold[i] = -1e16;
}
for(int j = 1; j <= k; j++){
if(j > 1){
M[csz] = qs[j-1];
C[csz] = dpold[j-1] - qs[j-1]*qs[j-1];
idx[csz] = j-1;
csz++;
while(csz >= 3 && bad(csz-3, csz-2, csz-1)){
M[csz-2] = M[csz-1];
C[csz-2] = C[csz-1];
idx[csz-2] = idx[csz-1];
csz--;
}
}
for(int i = j; i <= n; i++){
if(ptr >= csz) ptr = csz-1;
while(ptr < csz-1 && M[ptr+1]*qs[i] + C[ptr+1] > M[ptr]*qs[i] + C[ptr]) ptr++;
int id = ptr;
par[i][j] = idx[id];
dpnew[i] = M[id]*qs[i] + C[id];
M[csz] = qs[i];
C[csz] = dpold[i] - qs[i]*qs[i];
idx[csz] = i;
csz++;
while(csz >= 3 && bad(csz-3, csz-2, csz-1)){
M[csz-2] = M[csz-1];
C[csz-2] = C[csz-1];
idx[csz-2] = idx[csz-1];
csz--;
}
}
memcpy(dpold,dpnew,100005*sizeof(long long));
csz = ptr = 0;
}
printf("%lld\n",dpold[n]);
int x = n;
csz = 0;
for(int j = k; j > 1; j--){
x = par[x][j];
prt[csz++] = x;
}
for(int i = 0; i < csz; i++){
printf("%d ",prt[i]);
}
}
