#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = 1e5+5; const ll Km = 205; const ll INF = 1e18;
ll a[Nm];
ll psa[Nm+1];
//pii dp[Nm+1][Km+1]; //filled with zeroes initially: {value, previous index}
int dp[Nm+1][Km+1]; //just previous index now!
pii eval(array<ll,3> a1, ll x) {
return {a1[0]*x+a1[1],a1[2]};
}
//vector<array<ll,3>> adp[Km+1];
deque<array<ll,3>> adp[Km+1];
//more positive to more negative slopes
pii rd(deque<array<ll,3>>& v1, ll x) {
//read from front
if (v1.size()==1) {
return eval(v1.front(),x);
}
array<ll,3> t1 = v1.front(); v1.pop_front();
array<ll,3> t2 = v1.front();
pii p1 = eval(t1,x); pii p2 = eval(t2,x);
if (p2.first<p1.first) {
return rd(v1,x);
} else {
v1.push_front(t1); return p1;
}
}
void anl(deque<array<ll,3>>& v1) {
if (v1.size()<3) {
return;
}
array<ll,3> t3 = v1.back(); v1.pop_back();
array<ll,3> t2 = v1.back(); v1.pop_back();
array<ll,3> t1 = v1.back();
if (!((t3[1]*t1[0]+t1[1]*t2[0]+t2[1]*t3[0])>(t1[1]*t3[0]+t2[1]*t1[0]+t3[1]*t2[0]))) {
v1.push_back(t3);
anl(v1);
} else {
v1.push_back(t2);
v1.push_back(t3);
}
}
void wt(ll i, ll k, pii dpv) {
adp[k].push_back({-2*psa[i],dpv.first+2*psa[i]*psa[i],i});
anl(adp[k]);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
ll N,K; cin >> N >> K;
for (ll k=0;k<Km;k++) {
adp[k].push_back({0,INF,-1});
}
psa[0]=0;
for (ll i=0;i<N;i++) {
cin >> a[i];
psa[i+1]=psa[i]+a[i];
}
for (ll i=0;i<=N;i++) {
if (i==0) {
adp[0].push_back({0,0,0});
continue;
}
for (ll k=Km;k>=1;k--) {
//dp[i][k]=rd((adp[k-1]),psa[i]);
pii pdp = rd((adp[k-1]),psa[i]);
dp[i][k]=pdp.second;
if (pdp.first==INF) {
continue;
}
wt(i,k,pdp);
if (i==N && k==(K+1)) {
cout << (-pdp.first/2) <<"\n";
}
}
}
//cout << (-dp[N][K+1].first)/2 << "\n";
string ansS;
ll ip = N; ll kp = K+1;
vector<ll> vip;
while (kp>0) {
vip.push_back(ip);
ip = dp[ip][kp];
kp--;
}
for (ll k=0;k<K;k++) {
cout << vip[K-k];
if (k != (K-1)) {
cout << " ";
}
}
cout << ansS << "\n";
}
