#include<stdio.h>
#include<set>
typedef long long ll;
typedef std::pair<ll,ll> pl;
#define X first
#define Y second
int n, k, s[100010];
ll d[2][100010];
int b[202][100010];
int ans[202];
struct deq{
pl p[100010];
int w[100010];
int f, r;
void init(){f=r=0;}
void push(pl x,int c){
while(f-r>1 && (p[f-1].X - p[f-2].X) * (x.Y - p[f-1].Y) >= (x.X - p[f-1].X) * (p[f-1].Y - p[f-2].Y))--f;
p[f] = x, w[f++] = c;
}
ll pop(ll x){
while(f-r>1 && (x*p[r].X + p[r].Y) <= (x*p[r+1].X + p[r+1].Y))++r;
return x*p[r].X + p[r].Y;
}
inline int prev(){return w[r];}
}Deq[2];
int main()
{
scanf("%d%d",&n,&k);
int i;
for(i=1;i<=n;i++)scanf("%d",s+i);
for(i=1;i<=n;i++)s[i] += s[i-1];
for(int j=1;j<=k;j++){
int t = j&1;
Deq[t].init();
for(i=1;i<=n;i++){
d[t][i] = Deq[!t].pop(s[i]);
b[j][i] = Deq[!t].prev();
Deq[!t].push(pl(s[i], d[!t][i] - (ll)s[i]*s[i]), i);
}
}
printf("%lld\n",d[k&1][n]);
int now = n;
for(i=k;i;i--)now = b[i][now], ans[i] = now;
for(i=1;i<=k;i++)printf("%d ",ans[i]);
return 0;
}
