#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int mxN=1e5;
int n, k, a[mxN], last[mxN][201];
ll p[mxN+1], dp[mxN], dp2[mxN];
// p[i+1]x + dp[i] - p[i+1]*p[n]
double ix(int i, int j) {
ll a=p[i+1], b=dp[i]-p[i+1]*p[n];
ll c=p[j+1], d=dp[j]-p[j+1]*p[n];
return (double)(b-d)/(c-a);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (int i=0; i<n; ++i) {
cin >> a[i];
p[i+1]=p[i]+a[i];
}
for (int i=0; i<n; ++i) {
dp[i]=p[i+1]*(p[n]-p[i+1]);
last[i][0]=-1;
}
for (int i=1; i<=k; ++i) {
deque<int> dq;
auto Add=[&](int j) {
if (dq.size()&&!a[j])
return;
while(dq.size()>=2&&ix(dq.end()[-2], j)<ix(dq.end()[-2], dq.back()))
dq.pop_back();
dq.push_back(j);
};
memcpy(dp2, dp, sizeof(dp));
//for (int j=0; j<i; ++j)
Add(i-1);
for (int j=i; j<n; ++j) {
while(dq.size()>=2&&ix(dq[0], dq[1])<p[j+1])
dq.pop_front();
dp2[j]=p[j+1]*(p[n]-p[j+1])+p[j+1]*p[dq[0]+1]+dp[dq[0]]-p[dq[0]+1]*p[n];
last[j][i]=dq[0];
//cout << i << " " << j << " " << dq[0] << "\n";
Add(j);
}
memcpy(dp, dp2, sizeof(dp));
}
cout << dp[n-1] << "\n";
vector<int> ans(k);
for (int i=k, c=n-1; i; --i) {
c=last[c][i];
ans[i-1]=c;
}
for (int i : ans)
cout << i+1 << " ";
return 0;
}
