#pragma GCC optimize "-O3"
#include<bits/stdc++.h>
using namespace std;
const int N = 1000*100+5;
const long long INF = 1000000000000000000;
struct line{
long long k,b;
int id;
line():k(0),b(0),id(0){}
line(long long _k,long long _b,int _id):k(_k),b(_b),id(_id){}
};
struct node{
node* l;
node* r;
line ln;
node():l(NULL),r(NULL){}
};
long long f(line a, long long x) {
// if(a.k == 0 && a.b == 0) return INF;
return -(a.k*x+a.b);
}
const int maxn = 1000000000;
void add_line(line nw, node* v,int l = 0,int r = maxn){
int m = (l+r)/2;
bool lef = f(nw,l)<f(v->ln,l);
bool mid = f(nw,m)<f(v->ln,m);
if(mid){
swap(v->ln,nw);
}
if(l == r) return;
if(lef!=mid){
if(v->l == NULL) v->l = new node();
add_line(nw,v->l,l,m);
}
else{
if(v->r == NULL) v->r = new node();
add_line(nw,v->r,m+1,r);
}
}
pair<long long,int> get(int x, node* v,int l = 0,int r = maxn){
if(v == NULL) return {INF,0};
if(l == r) return {f(v->ln,x),v->ln.id};
int m = (l+r)/2;
if(x<m){
return min({f(v->ln,x),v->ln.id},get(x,v->l,l,m));
}
else return min({f(v->ln,x),v->ln.id},get(x,v->r,m+1,r));
}
void clean(node* v){
if(v->l!=NULL) clean(v->l);
if(v->r!=NULL) clean(v->r);
v->ln = line(0,0,0);
}
void havasar(node* x,node* y){
x->ln = y->ln;
if(y->l!=NULL){
if(x->l == NULL) x->l = new node();
havasar(x->l,y->l);
}
if(y->r!=NULL){
if(x->r == NULL) x->r = new node();
havasar(x->r,y->r);
}
}
int a[N];
long long pref[N];
pair<long long,int> dp[208][N];
int par[208][N];
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
for(int i = 1;i<=n;i++) pref[i] = pref[i-1]+a[i];
node* old = new node();
node* nold = new node();
for(int kk = 1;kk<=k;kk++){
for(int i = kk;i<=n;i++){
/*if(kk == 1){
for(int j = dp[kk-1][i].second;j<i;j++){
if(dp[kk-1][j].first+(pref[i]-pref[j])*pref[j]>=dp[kk][i].first){
dp[kk][i].first = dp[kk-1][j].first+(pref[i]-pref[j])*pref[j];
dp[kk][i].second = j;
}
}
line now = line({pref[i],dp[kk][i].first-pref[i]*pref[i],i});
add_line(now,nold);
continue;
}*/
pair<long long,int> u = get(pref[i],old);
dp[kk][i].first = -u.first;
dp[kk][i].second = u.second;
line now = line({pref[i],dp[kk][i].first-pref[i]*pref[i],i});
add_line(now,nold);
if(kk == 1) add_line(line(pref[i],-pref[i]*pref[i],i),old);
}
havasar(old,nold);
clean(nold);
}
printf("%lld\n",dp[k][n].first);
if(dp[k][n].first == 0){
for(int i = 1;i<=k;i++) cout<<i<<endl;
return 0;
}
int kk = k;
int nn = n;
while(kk>0){
printf("%d\n",dp[kk][nn].second);
nn = dp[kk][nn].second;
kk--;
}
printf("\n");
return 0;
}
