#include<bits/stdc++.h>
using namespace std;
const int nax = 1e5 + 2;
const long long INF = 1e18;
int n, k;
long long a[nax], p[nax];
int par[nax][203];
struct line{
long long m, c, id;
line() {}
line(long long _m, long long _c, long long _id) {
m = _m, c = _c, id = _id;
}
long long eval(long long x) {
return m * x + c;
}
};
long long isecx(line a, line b) {
return (long double) (b.c - a.c) / (long double) (a.m - b.m);
}
struct CHT{
int sz = 0;
deque<line>dq;
void insert(line newLine) {
while(sz>=2 && isecx(dq[0], dq[1])<=isecx(newLine, dq[0])) {
dq.pop_front();
--sz;
}
dq.push_front(newLine);
++sz;
}
pair<long long, long long> query(long long x) {
while(sz>=2 && dq[sz-1].eval(x)<=dq[sz-2].eval(x)) {
dq.pop_back();
--sz;
}
return make_pair(dq[sz-1].eval(x), dq[sz-1].id);
}
};
void PlayGround() {
cin>>n>>k;
for(int i=1; i<=n; ++i) {
cin>>a[i];
}
for(int i=1; i<=n; ++i) {
p[i] = p[i-1] + a[i];
}
vector<long long>dp(nax);
for(int j=1; j<=k+1; ++j) {
vector<long long>new_dp(nax);
CHT myCHT;
myCHT.insert(line(-p[j-1], dp[j-1], j-1));
for(int i=j; i<=n; ++i) {
long long x = p[n] - p[i];
auto [y, id] = myCHT.query(x);
long long cons = p[i] * (p[n] - p[i]);
new_dp[i] = cons + y;
myCHT.insert(line(-p[i], dp[i], i));
par[i][j] = id;
}
dp.swap(new_dp);
}
cout<<dp[n]<<'\n';
vector<int>config;
int cur = n, j = k+1;
int cnt = k;
while(1) {
cur = par[cur][j];
--j;
cout<<cur<<' ';
--cnt;
if(cnt==0) break;
}
// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
PlayGround();
return 0;
}
