#include<bits/stdc++.h>
using namespace std;
int tip;
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 long long maxn = 10000000;
long long n;
void add_line(line nw, node* v, long long l = 0, long long r = maxn) {
long long 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(r - l == 1) return;
else 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, r);
}
}
bool operator<(pair<long long,int> a,pair<long long,int> b){
return a.first<b.first;
}
pair<long long,int> get(long long x, node* v, long long l = 0, long long r = maxn) {
long long m = (l + r) / 2;
if(r - l == 1) {
if(v == NULL) v = new node();
return make_pair(f(v->ln, x),v->ln.id);
}
else if(x < m) {
if(v->l == NULL) v->l = new node();
pair<long long,int> xx = make_pair(f(v->ln,x),v->ln.id);
pair<long long,int> y = get(x,v->l,l,m);
return min(xx,y);
}
else {
if(v->r == NULL) v->r = new node();
pair<long long,int> xx = make_pair(f(v->ln,x),v->ln.id);
pair<long long,int> y = get(x, v->r, m, r);
return min(xx,y);
}
}
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];
//int suf[N];
pair<long long,int> dp[208][N];
int par[208][N];
int main()
{
int n,k;
cin>>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];
// for(int i = n;i>=1;i--) suf[i] = suf[i+1]+a[i];
node* old = new node();
node* nold = new node();
for(int kk = 1;kk<=k;kk++){
tip = kk;
for(int i = kk+1;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);
}
havasar(old,nold);
clean(nold);
}
cout<<dp[k][n].first<<endl;
int kk = k;
int nn = n;
while(kk>0){
cout<<dp[kk][nn].second<<" ";
nn = dp[kk][nn].second;
kk--;
}
cout<<endl;
return 0;
}
