#include <iostream>
#include <queue>
#include <vector>
#define f first
#define s second
using namespace std;
long long n, k, ps[100010], dp[210], cur;
int p[100010][210];
deque<pair<pair<long double,pair<long long,long long>>,int>> dq[210];
long double pt(long double m1, long double c1, long double m2, long double c2) {
return (c2-c1)/(m1-m2);
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> ps[i];
ps[i] += ps[i-1];
}
for (int i = 1; i < n; i++) {
for (int j = k; j >= 1; j--) {
if (j == 1) {
if ((j == k) && (dp[j] <= ps[i]*(ps[n]-ps[i]))) cur = i;
dp[j] = max(dp[j],ps[i]*(ps[n]-ps[i]));
} else {
while ((dq[j-1].size()) && (dq[j-1].front().f.f < ps[i])) dq[j-1].pop_front();
if (dq[j-1].size()) {
if (dp[j] < dq[j-1].front().f.s.f*ps[i]+dq[j-1].front().f.s.s+ps[n]*ps[i]-ps[i]*ps[i]) {
if (j == k) cur = i;
p[i][j] = dq[j-1].front().s;
} else p[i][j] = p[i-1][j];
dp[j] = max(dp[j],dq[j-1].front().f.s.f*ps[i]+dq[j-1].front().f.s.s+ps[n]*ps[i]-ps[i]*ps[i]);
}
}
if ((dq[j].size()) && (ps[i] == dq[j].back().f.s.f)) {
if (dq[j].back().f.s.f > dp[j]-ps[n]*ps[i]) goto skip;
else dq[j].pop_back();
}
while ((dq[j].size() >= 2) && (dq[j][dq[j].size()-2].f.f > pt(dq[j][dq[j].size()-2].f.s.f,dq[j][dq[j].size()-2].f.s.s,ps[i],dp[j]-ps[n]*ps[i]))) dq[j].pop_back();
if (dq[j].size()) dq[j].back().f.f = pt(dq[j].back().f.s.f,dq[j].back().f.s.s,ps[i],dp[j]-ps[n]*ps[i]);
if (dp[j] != 0) dq[j].push_back({{1e18,{ps[i],dp[j]-ps[n]*ps[i]}},i});
skip:;
}
}
cout << dp[k] << endl;
for (int i = k; i >= 1; i--) {
cout << cur << " ";
cur = p[cur][i];
}
cout << endl;
}
/*
7 3
4 1 3 4 0 2 3
*/
