#include <bits/stdc++.h>
using namespace std;
// long long dv(long long a, long long b) { return a / b - ((a^b)<0 && a%b); }
/* struct Line {
long long a, b; int id;
Line(long long _a, long long _b, int _id) : a(_a), b(_b), id(_id) {}
long long intersect(Line L) { return dv(L.b-b, a-L.a); }
// double intersect(const Line& L) const { return (double)(L.b-b) / (a-L.a); }
long long eval(long long x) { return a*x + b; }
}; */
/*
struct CHT {
deque<Line> cht;
void add(Line L) {
if(cht.size() && cht.front().a == L.a) {
if(cht.front().b > L.b) return;
cht.pop_front();
}
while(cht.size() >= 2 && L.intersect(cht[1]) <= L.intersect(cht[0]))
cht.pop_front();
cht.push_front(L);
}
Line query(int x) {
Line ans(-1, -1, -1);
for(Line l : cht)
if(l.eval(x) > ans.eval(x)) ans = l;
return ans;
// while(cht.size() >= 2 && cht[ cht.size() - 2 ].eval(x) >= cht.back().eval(x))
// cht.pop_back();
// return cht.back();
}
} cht;
*/
constexpr __int128 inf = ((__int128)0x3f3f3f3f3f3f3f3f) * ((__int128)0x3f3f3f3f3f3f3f3f);
struct Line
{
__int128 a, b, x; int id; // vou codar com inteiros msm
Line(__int128 _a = 0, __int128 _b = 0, __int128 _x = inf, int _id = 0) : a(_a), b(_b), x(_x), id(_id) {}
bool operator<(const Line& o) const { return a < o.a; } // change < for >, for min queries
bool operator<(const __int128& o) const { return x < o; }
__int128 eval(__int128 qr) { return a*qr + b; }
};
struct LineContainer : multiset<Line, less<>>
{
bool hasNext(iterator it) { return next(it) != end(); }
bool hasPrev(iterator it) { return it != begin(); }
__int128 div(__int128 a, __int128 b) { return a / b - ((a^b)<0 && a%b); }
__int128 intersect(Line l1, Line l2) { return div(l1.b-l2.b, l2.a-l1.a); }
// double intersect(Line l1, Line l2) { return (double)(l1.b-l2.b)/(l2.a-l1.a); }
bool bad(Line l1, Line l2, Line l3) { return intersect(l1, l3) <= intersect(l1, l2); }
iterator get_x(iterator it) {
if(!hasNext(it)) return it;
Line l = *it;
l.x = intersect(l, *next(it));
erase(it);
return insert(l);
}
void add(Line l) {
auto it = lower_bound(l);
__int128 a = l.a, b = l.b;
if(it != end() && it->a == a) {
if(it->b >= b) return;
erase(it);
}
it = insert(l);
if(hasPrev(it) && hasNext(it) && bad(*prev(it), *it, *next(it)))
return (void)(erase(it));
while(hasPrev(it) && hasPrev(prev(it)) && bad(*prev(prev(it)), *prev(it), *it))
erase(prev(it));
while(hasNext(it) && hasNext(next(it)) && bad(*it, *next(it), *next(next(it))))
erase(next(it));
it = get_x(it);
if(hasPrev(it)) get_x(prev(it));
}
Line query(long long x) {
assert(!empty());
auto it = lower_bound(x);
return *it;
}
} cht;
constexpr int maxn = 2e5+10, maxk = 210;
int a[maxn];
long long suf[maxn];
long long dp[2][maxn];
int opt[maxk][maxn];
int32_t main() {
int n, k; scanf("%d %d", &n, &k);
for(int i = 1; i <= n; i++)
scanf("%d", a+i);
// dp[i] = dp[j] + suf[i+1] * (suf[j+1] - suf[i+1])
// dp[i] = dp[j] + {suf[j+1] * suf[i+1]} - (suf[i+1]^2)
for(int i = n; i >= 1; i--)
suf[i] = a[i] + suf[i+1];
for(int i = 1; i <= k; i++) {
cht.clear();
cht.add(Line(suf[1], 0, inf, -1));
for(int j = 1; j <= n; j++) {
Line bom = cht.query(suf[j+1]);
opt[i][j] = bom.id;
dp[1][j] = bom.eval(suf[j+1]) - 1ll*suf[j+1]*suf[j+1];
cht.add(Line(suf[j+1], dp[0][j], inf, j));
}
for(int j = 1; j <= n; j++)
dp[0][j] = dp[1][j], dp[1][j] = 0;
}
long long ans = 0;
for(int j = 1; j < n; j++)
if(dp[0][j] >= dp[0][ans]) ans = j;
printf("%lld\n", dp[0][ans]);
for(int i = 0; i < k; i++)
assert(ans >= 0), printf("%lld ", ans), ans = opt[k-i][ans];
puts("");
}
