#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
struct Line {
mutable long long k, m, p; // slope, intercept, last x where this line is best
int id; // label/index
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(long long x) const { return p < x; } // for lower_bound(x)
};
struct LineContainer : std::multiset<Line, std::less<>> {
static const long long INF = (1LL<<62);
static long long floordiv(long long a, long long b) {
long long q = a / b, r = a % b;
if (r && ((a ^ b) < 0)) --q;
return q;
}
// sets x->p = last x where x is >= y; returns true if x->p >= y->p (y is useless)
bool isect(iterator x, iterator y) {
if (y == end()) { x->p = INF; return false; }
if (x->k == y->k) {
// same slope: keep the better intercept; if equal, keep higher id
if (x->m > y->m || (x->m == y->m && x->id > y->id)) x->p = INF;
else x->p = -INF;
} else {
// last integer x where x is better than y
x->p = floordiv(y->m - x->m, x->k - y->k);
}
return x->p >= y->p;
}
// Before inserting, kill worse equal-slope neighbors (keep larger m, tie -> higher id)
void add(long long k, long long m, int id) {
Line L{ k, m, 0, id };
// Remove dominated equal-slope line if present
auto it = lower_bound(k); // first with slope >= k
if (it != end() && it->k == k) {
if (it->m > m || (it->m == m && it->id >= id)) return; // existing is better
it = erase(it); // new one is >=, so remove old
} else if (it != begin()) {
auto it2 = std::prev(it);
if (it2->k == k) {
if (it2->m > m || (it2->m == m && it2->id >= id)) return;
erase(it2);
}
}
auto z = insert(L), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
}
// Query max at x; if tie on value, prefer higher id.
std::pair<int,long long> query(long long x) const {
assert(!empty());
auto it = lower_bound(x); // best candidate by breakpoints
long long bestVal = it->k * x + it->m;
int bestId = it->id;
// Tie-break check with neighbors: only adjacent lines can tie at a point.
// Check predecessor
if (it != begin()) {
auto pr = std::prev(it);
long long v = pr->k * x + pr->m;
if (v == bestVal && pr->id > bestId) {
bestId = pr->id;
// bestVal unchanged
}
}
// Check successor
auto nx = std::next(it);
if (nx != end()) {
long long v = nx->k * x + nx->m;
if (v == bestVal && nx->id > bestId) {
bestId = nx->id;
}
}
return {bestId, bestVal};
}
};
// to use:
// LineContainer hull;
// hull.add(m, c);
// hull.query(x);
// to convert max queries to min queries:
// hull.add(-m, -c);
// -hull.query(x);
int n,k;
signed main(){
cin>>n>>k;
vector<int> v(n+1,0), p(n+1, 0);
for(int i=1;i<=n;i++){
cin>>v[i];
p[i]=p[i-1]+v[i];
}
vector<vector<int>> dp(n+1, vector<int>(k+1, 0));
vector<vector<pair<int,int>>> from(n+1, vector<pair<int,int>>(k+1));
int ans=LLONG_MIN,a=0,b=0;
for(int m=1;m<=k;m++){
LineContainer hull;
for(int i=1;i<=n;i++){
hull.add(p[i-1], dp[i-1][m-1]-p[i-1]*p[n], i-1);
auto [id, best]=hull.query(p[i]);
int add=-p[i]*p[i]+p[i]*p[n];
dp[i][m]=best+add;
from[i][m]={id, m-1};
if(dp[i][m] > ans){
ans=dp[i][m];
a=i,b=m;
}
//~ printf("i:%lld, splits:%lld, best %lld add %lld\n",i,m,best,add);
//~ printf("added m=%lld, c=%lld\n", p[i], dp[i][m]-p[i]*p[n]);
}
}
cout<<ans<<'\n';
int ca=a, cb=b,cnt=0;
while(ca>0 and cb>0){
cnt++;
tie(ca,cb)=from[ca][cb];
}
assert(cnt==k);
while(a>0 and b>0){
cout<<a<<" ";
tie(a,b)=from[a][b];
}
}
/*
4 2
3 1 2 3
*/
