#include <cstdio>
#include <vector>
#include <utility>
#include <tuple>
#include <cassert>
#define F first
#define S second
#define SZ(x) ((int)x.size())
using namespace std;
template<class T>
struct CHT {
using pt = pair<T,T>;
vector<pt> ln;
vector<int> idx;
int curr = 0;
bool bad(pt& a, pt& b, T x) {
return (b.S - a.S) >= x * (a.F - b.F);
}
bool bad(pt& a, pt& b, pt& c) {
return (b.S - a.S) * (b.F - c.F) >= (c.S - b.S) * (a.F - b.F);
}
void insert(pt v, int i) {
if(SZ(ln) > 0 && ln.back().F == v.F) {
if(ln.back().S > v.S) return;
else ln.pop_back(), idx.pop_back();
}
while(SZ(ln) >= 2 && bad(ln[SZ(ln)-2], ln.back(), v))
ln.pop_back(), idx.pop_back();
ln.push_back(v), idx.push_back(i);
}
pair<T, int> query(T x) {
assert(SZ(ln) > 0);
curr = min(curr, SZ(ln) - 1);
while(curr < SZ(ln) - 1 && bad(ln[curr], ln[curr+1], x))
curr++;
return {x * ln[curr].F + ln[curr].S, idx[curr]};
}
void clear() {
ln.clear();
idx.clear();
curr = 0;
}
};
int n, k, rec[100010][202];
long long s[100010], dp[100010], currDP;
CHT<long long> cht;
int main() {
scanf("%d%d", &n, &k);
for(int i=1; i<=n; i++) scanf("%lld", s+i), s[i] += s[i-1];
for(int j=2; j<=k+1; j++) {
cht.clear();
cht.insert({s[j-1], dp[j-1] - s[j-1]*s[j-1]}, j-1);
for(int i=j; i<=n; i++) {
tie(currDP, rec[i][j]) = cht.query(s[i]);
cht.insert({s[i], dp[i] - s[i]*s[i]}, i);
dp[i] = currDP;
}
}
long long ans = 0;
//printf("%lld\n", dp[n]);
int p = n;
vector<int> res;
while(k > 0) {
res.push_back(rec[p][k+1]);
p = rec[p][k+1], k--;
}
for(int i=SZ(res)-1; i>=0; i--)
ans += (s[res[i]] - (i<SZ(res)-1 ? s[res[i+1]] : 0)) * (s[n] - s[res[i]]);
printf("%lld\n", ans);
for(int i=SZ(res)-1; i>=0; i--) printf("%d ", res[i]);
return 0;
}
