#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
int n, k, trace[maxn + 1][201];
long long bestPos = 0, res = LLONG_MIN/4, pre[maxn + 1];
const long long NEG = LLONG_MIN/4;
struct Line {
long long m; // slope (a)
long long b; // intercept (b)
int id;
Line(long long _m=0, long long _b=0, int _id=0): m(_m), b(_b), id(_id) {}
};
// check if l2 is unnecessary between l1 and l3
inline bool bad(const Line &l1, const Line &l2, const Line &l3){
// (b3 - b1) / (m1 - m3) <= (b2 - b1) / (m1 - m2)
// Cross multiply to avoid floating point.
long long left = (long long)(l3.b - l1.b) * (long long)(l1.m - l2.m);
long long right = (long long)(l2.b - l1.b) * (long long)(l1.m - l3.m);
return left <= right;
}
struct CHT {
vector<Line> hull;
int ptr = 0; // pointer for queries with non-decreasing x
void clear(){ hull.clear(); ptr = 0; }
// slopes must be added in non-decreasing order
void add(Line L){
// if last slope == new slope, keep the one with bigger intercept
while(!hull.empty() && hull.back().m == L.m){
if (hull.back().b >= L.b) return; // new line dominated
else hull.pop_back(); // remove dominated last line
}
while(hull.size() >= 2 && bad(hull[hull.size()-2], hull.back(), L))
hull.pop_back();
hull.push_back(L);
if (ptr >= (int)hull.size()) ptr = (int)hull.size() - 1;
}
// query maximum at x; x must be non-decreasing between queries
pair<long long,int> query(long long x){
if (hull.empty()) return {NEG, 0};
while(ptr + 1 < (int)hull.size()){
long long v1 = (long long)hull[ptr].m * x + (long long)hull[ptr].b;
long long v2 = (long long)hull[ptr+1].m * x + (long long)hull[ptr+1].b;
if (v2 >= v1) ++ptr;
else break;
}
long long val = (long long)((long long)hull[ptr].m * x + (long long)hull[ptr].b);
return {val, hull[ptr].id};
}
};
// number of levels max k is up to 200 -> allocate 201
CHT lc;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
if (!(cin >> n >> k)) return 0;
for (int i = 1; i <= n; ++i){
cin >> pre[i];
pre[i] += pre[i - 1];
}
for (int i = 0; i <= n; ++i){
for (int j = 0; j <= k; ++j) trace[i][j] = 0;
}
vector<long long> dp(n + 1, -1e18);
for (int i = 1; i <= n; ++i) dp[i] = pre[i] * (pre[n] - pre[i]);
for (int j = 1; j < k; ++j){
vector<long long> cur(n + 1, -1e18);
lc.clear();
for (int i = 1; i <= n; ++i){
if (i >= j){
pair<long long, long long> g = lc.query(pre[i] - pre[n]);
if (g.first != -1e18) cur[i] = g.first + pre[i] * (pre[n] - pre[i]);
trace[i][j] = g.second;
}
if (dp[i] != -1e18) lc.add(Line(pre[i], dp[i], i));
}
swap(dp, cur);
}
for (int i = k; i <= n; ++i){
if (dp[i] > res){
res = dp[i];
bestPos = i;
}
}
cout << res << '\n';
vector<int> cuts;
while (bestPos != 0 && k > 0) {
cuts.push_back((int)bestPos);
bestPos = trace[bestPos][k];
--k;
}
reverse(cuts.begin(), cuts.end());
for (int i = 0; i < (int)cuts.size(); ++i){
if (i) cout << ' ';
cout << cuts[i];
}
cout << '\n';
return 0;
}
