#include<bits/stdc++.h>
using namespace std;
const long long NEG = LLONG_MIN/4;
struct Line {
long long m, b;
int id;
Line(long long _m=0, long long _b=0, int _id=0): m(_m), b(_b), id(_id) {}
};
inline bool bad(const Line &l1, const Line &l2, const Line &l3){
return (l3.b - l1.b) * (l1.m - l2.m) <= (l2.b - l1.b) * (l1.m - l3.m);
}
struct CHT {
vector<Line> hull;
int ptr = 0;
void clear(){ hull.clear(); ptr = 0; }
void add(Line L){
while(!hull.empty() && hull.back().m == L.m){
if (hull.back().b >= L.b) return;
hull.pop_back();
}
while(hull.size() >= 2 && bad(hull[hull.size()-2], hull.back(), L))
hull.pop_back();
hull.push_back(L);
ptr = min(ptr, (int)hull.size()-1);
}
Line query(long long x){
while(ptr + 1 < (int)hull.size() &&
hull[ptr].m * x + hull[ptr].b <= hull[ptr+1].m * x + hull[ptr+1].b)
ptr++;
return hull[ptr];
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<long long> pre(n + 1, 0);
for (int i = 1; i <= n; ++i){
cin >> pre[i];
pre[i] += pre[i - 1];
}
CHT current, next;
vector<vector<int>> trace(k + 1, vector<int>(n + 1, 0));
current.add(Line(0, 0, 0));
long long res = LLONG_MIN;
int bestEnd = -1;
for (int j = 1; j <= k; ++j){
next.clear();
for (int i = j; i <= n; ++i){
Line best = current.query(pre[i] - pre[n]);
if (best.b == NEG) continue;
long long dp = best.b + pre[i] * (pre[n] - pre[i]);
trace[j][i] = best.id;
if (j < k) {
next.add(Line(pre[i], dp, i));
}
if (j == k && i < n && dp > res){
res = dp;
bestEnd = i;
}
}
swap(current, next);
}
cout << res << '\n';
vector<int> cuts;
int cur = bestEnd;
for (int j = k; j >= 1 && cur > 0; --j){
cuts.push_back(cur);
cur = trace[j][cur];
}
reverse(cuts.begin(), cuts.end());
for (int i = 0; i < (int)cuts.size(); ++i){
if (i) cout << ' ';
cout << cuts[i];
}
cout << '\n';
return 0;
}
