#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#define bupol __builtin_popcount
//#define int long long
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 1e5+5;
const int MAXK = 205;
const int LOG = 20;
const int MOD = 1e9+7;
const int SQRT = 520;
const ll INF = 2e18;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> ipii;
int n, k;
int a[MAXN], pr[MAXN];
ll dp[MAXN][3]; int ba[MAXN][MAXK];
struct Line {
ll m, c, idx = -1;
ll gety(ll x){
return m*x+c;
}
};
pii getmid(Line nw, Line oth){
return pii(nw.c-oth.c, oth.m-nw.m);
}
bool cmp(Line x, Line y, Line z){
// ld back = (z.c-y.c) / (y.m-z.m);
// ld nw = (z.c-x.c) / (x.m-z.m);
pii le = getmid(x, y); pii ri = getmid(y, z);
//if(le.se==0 || ri.se==0) assert(false);
return 1ll * le.fi * ri.se < 1ll * ri.fi * le.se; // expected nw lebih gede
}
vector <Line> ch;
void ins(Line x){
while(ch.size()>=2){
if(ch.back().m == x.m && ch.back().c == x.c ) return;
if(!cmp(ch[(int)ch.size()-2], ch.back(), x) ){
ch.pop_back();
} else break;
}
ch.pb(x);
}
pii que(int x){
ll ans = -1;
ll ret = -INF;
// for(int i=0; i<ch.size(); i++){
// ll le = ch[i].gety(x);
// if(ret < le){
// ret = le; ans = ch[i].idx;
// }
// }
// return pii(ret, ans);
if(ch.size() == 0) return pii(0, -1);
if(ch.size() == 1){
return pii(ch[0].gety(x), ch[0].idx);
}
int l=1, r=(int)ch.size()-1, mid = 0;
while(l-1<=r){
mid = (l+r)/2;
ll le = -1;
if(0<=mid-1 && mid-1<(int)ch.size()){
le = ch[mid-1].gety(x);
if(ret < le){
ret = le; ans = ch[mid-1].idx;
}
}
ll ri = -1;
if(0<=mid && mid<(int)ch.size()){
ri = ch[mid].gety(x);
if(ret < ri){
ret = ri; ans = ch[mid].idx;
}
}
if(le < ri) l = mid+2; // ke kanan
else r = mid-2;
}
return pii(ret, ans);
}
signed main(){
//ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> k;
for(int i=1; i<=n; i++){
cin >> a[i]; pr[i] = pr[i-1]+a[i];
}
for(int m=1; m<=k; m++){
ch.clear();
for(int i=1; i<=n; i++){
//for(int j=1; j<=i-1; j++) dp[i][m%2] = max(dp[i][m%2], (dp[j][(m-1)%2] - pr[j]*pr[j]) + pr[i] * pr[j]);
pii te = que(pr[i]);
dp[i][m%2] = te.fi;
ba[i][m] = te.se;
//if(te.se > n) assert(false);
if(i>=m){
Line line;
line.idx = i;
line.m = pr[i];
line.c = dp[i][(m-1)%2] - 1ll * pr[i]*pr[i];
ins(line);
}
//cout << dp[i][m%2] << " \n"[i==n];
}
// for 1->n, j<i
// dp[i][m] = (dp[j][m-1] - pr[j]*pr[j]) + pr[i] * pr[j]
// y = c + x * m
}
cout << dp[n][k%2] << '\n';
int nw = n;
for(int m=k; m>=1; m--){
nw = ba[nw][m];
//cout << dp[i][m] <<' ' << i << ' ' << m << '\n';
if(nw==-1){
cout << "jnc\n"; exit(0);
}
cout << nw << ' ';
}
cout << '\n';
}
