#include<bits/stdc++.h>
#define int long long
using namespace std;
/*
struct CHT{
struct line{
int m,c,id;
line(int mm=0,int cc=0,int i=0){
m=mm;
c=cc;
id=i;
}
int cal(int x){
return m*x+c;
}
double intersect(line l){
return 1.0*(c-l.c)/(l.m-m);
}
};
deque<pair<line,double>> dq;
void insert(int m,int c,int i){
line nline(m,c,i);
while(dq.size()>1&&dq.back().second>=dq.back().first.intersect(nline))
dq.pop_back();
if(dq.empty())
dq.push_back({nline,0});
else
dq.push_back({nline,nline.intersect(dq.back().first)});
}
pair<int,int> query(int x){
while(dq.size()>1){
if(dq[1].second<=x)
dq.pop_front();
else
break;
}
return {dq.front().first.cal(x),dq.front().first.id};
}
void init(){
dq.clear();
insert(0,0,0);
}
};
*/
struct line{
int m,c,id;
line(int mm=0,int cc=0,int i=0){
m=mm;
c=cc;
id=i;
}
int cal(int x){
return m*x+c;
}
int intersect(line l){
return (c-l.c)/(l.m-m);
}
};
int n,k;
int s[100005];
int dp[100005],ndp[100005];
int prv[100005][300];
main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
for(int i=1;i<=n;i++){
cin >> s[i];
s[i]+=s[i-1];
}
++k;
for(int j=1;j<=k;j++){
/*
CHT cht;
cht.init();
for(int i=1;i<=n;i++){
pair<int,int> pi=cht.query(s[i]);
ndp[i]=s[n]*s[i]-s[i]*s[i]+pi.first;
prv[i][j]=pi.second;
cht.insert(s[i],-s[i]*s[n]+dp[i],i);
}
dp=ndp;
*/
deque<line> dq;
dq.push_back(line());
for(int i=1;i<=n;i++){
while(dq.size()>1&&dq.back().cal(s[i])<=dq[dq.size()-2].cal(s[i]))
dq.pop_back();
ndp[i]=dq.back().cal(s[i])+s[n]*s[i]-s[i]*s[i];
prv[i][j]=dq.back().id;
line nline=line(s[i],-s[i]*s[n]+dp[i],i);
if(!dq.empty()&&dq.front().m==nline.m){
if(nline.c>=dq.front().c)
dq.pop_front();
else
continue;
}
while(dq.size()>1&&nline.intersect(dq.front())<=dq[1].intersect(dq.front()))
dq.pop_front();
dq.push_front(nline);
}
for(int i=1;i<=n;i++)
dp[i]=ndp[i];
}
cout << dp[n] << "\n";
int cur=n;
for(int j=k;j>=2;j--){
cur=prv[cur][j];
cout << cur << " ";
}
}
/*
7 3
4 1 3 4 0 2 3
*/
