#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt")
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
const int mxn = 1e5+2;
ll N,K;
pair<pll,int> dp[mxn];
ll pref[mxn];
ll S;
struct line{
int id,cnt;
ll m,b;
pll operator()(ll k){
return pll(m*k+b,cnt-1);
}
line(){}
line(ll a,ll bb,int ii,int cc){
m = a,b = bb;
id = ii;
cnt = cc;
}
};
deque<line> dq;
bool btw(line a,line b,line c){
if(b.m == c.m&&b.b<c.b)return true;
if(a.m == b.m&&a.b>b.b)return true;
return (a.b-b.b)*(c.m-b.m)>(b.b-c.b)*(b.m-a.m);
}
pll run(ll tax){
while(!dq.empty())dq.pop_back();
line tt = line(0ll,0ll,0,0);
dq.push_back(tt);
for(int i = 1;i<=N;i++){
while(dq.size()>1&&dq[0](pref[i])<=dq[1](pref[i]))dq.pop_front();
dp[i].fs.fs = dq[0](pref[i]).fs+S*pref[i]-pref[i]*pref[i]-tax;
dp[i].fs.sc = dq[0](pref[i]).sc;
dp[i].sc = dq[0].id;
line tmp = line(pref[i]*2,dp[i].fs.fs-pref[i]*pref[i]-S*pref[i],i,dp[i].fs.sc);
while(dq.size()>1&&btw(dq.end()[-2],dq.end()[-1],tmp))dq.pop_back();
dq.push_back(tmp);
}
return dp[N].fs;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N>>K;
for(int i = 1;i<=N;i++){
cin>>pref[i];
pref[i] += pref[i-1];
}
srand(time(NULL));
S = pref[N];
ll l = -1e12,r = 1e12;
while(l != r){
ll mid = l+(r-l)/2;
auto re = run(mid);
re.sc = -re.sc;
//cout<<mid<<":"<<re.fs<<','<<re.sc<<endl;
if(re.sc<=K+1)r = mid;
else l = mid+1;
}
run(l);
int pos = N;
ll val = dp[N].fs.fs+(K+1)*l;
vector<int> v;
for(int i = K+1;i>1;i--){
pos = dp[pos].sc;
v.push_back(pos);
}
assert(v.size() == K);
/*
cout<<S<<endl;
for(int i = 0;i<=K;i++){
for(int j = 0;j<=N;j++)cout<<dp[i][j].fs<<' '<<dp[i][j].sc<<',';cout<<endl;
}
*/
cout<<val/2<<'\n';
for(auto &i:v)cout<<i<<' ';cout<<'\n';
}
