#include<stdio.h>
int dat[100001], sum[100001];
long long dp[2][100001];
long long Y[100001];
int p[210][100001];
void mkt(long long *T, long long *S, int *p, int f, int r, int s, int e)
{
if(f>r) return;
long long max = -1, t;
int x = -1, i, m = (f+r)/2;
for(i=s; i<=e && i<m; i++)
{
if(S[i] == -1) continue;
t = S[i] + (1ll*sum[i]*(sum[m] - sum[i]));
if(t>=max)
{
max = t;
x = i;
}
}
T[m] = max;
p[m] = x;
mkt(T, S, p, f, m-1, s, x);
mkt(T, S, p, m+1, r, x, e);
}
int main()
{
int n, k, i, j;
scanf("%d%d", &n, &k); k++;
for(i=1; i<=n; i++)
{
scanf("%d", &dat[i]);
sum[i] = sum[i-1] + dat[i];
}
for(i=0; i<=1; i++)for(j=0; j<=n; j++) dp[i][j]=-1;
for(j=0; j<=n; j++) dp[1][j] = 0;
for(i=2; i<=k; i++)
{
for(j=0; j<=n; j++) dp[i%2][j] = -1;
mkt(dp[i%2], dp[(i+1)%2], p[i], 0, n, 0, n);
}
printf("%lld\n", dp[k%2][n]);
int x = n;
for(int i=k; i>1; i--)
{
x = p[i][x];
printf("%d ", x);
}
return 0;
}
