#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N = 2e5+5, mod = 1e9+7, sq = 500;
int n,cnt;
ll k[N],A[N],b[N],pre[N],q[N];
ll dp[2][N], where[205][N];
int l,r;
ll get(int x,ll i){
return k[i]*x + b[i];
}
/*bool check1(int x,int y,int i){
assert(x > 0);
ll a = pre[n]-pre[i];
//k[x]*a+b[x] <= k[y]*a+b[y]
//a*(k[y]-k[x]) >= b[x] - b[y];
return a*(k[y]-k[x]) >= b[x] - b[y];
return get(pre[n]-pre[i],x) <= get(pre[n]-pre[i],y);
}
bool check2(int x,int y,ll i){
//xi = (b[x]-b[i])/(k[i]-k[x])
//xy = (b[x]-b[y])/(k[y]-k[x])
//xi >= xy
assert(x > 0);
if(k[y] == k[i]) return (b[i] >= b[y]);
//assert(k[y] != k[x]);
if(k[y] == k[x]) return 1;
assert(k[i] != k[x]);
return (b[x]-b[i])*(k[y]-k[x]) >= (b[x]-b[y])*(k[i]-k[x]);
}*/
bool check1(int x, int y, int i) {
return (dp[0][y] - dp[0][x] >=
(pre[y] - pre[x]) * (pre[n] - pre[i]));
}
bool check2(int x, int y, int i) {
return ((dp[0][y] - dp[0][x]) * (pre[i] - pre[y]) <=
(dp[0][i] - dp[0][y]) * (pre[y] - pre[x]));
}
inline void test_case(){
cin >> n >> cnt; assert(n <= 1e5 && cnt <= 200);
for(int i = 1; i <= n; i++){
cin >> A[i];
pre[i] = pre[i-1] + A[i];
}
pre[n+1] = pre[n];
//cout << pre[1] << endl;
for(int j = 1; j <= cnt+1; j++){
q[1] = 0; l = 1, r = 2;
k[1] = 0, b[1] = 0;
for(int i = 1; i <= n; i++){
while(r-l > 1 && check1(q[l],q[l+1],i))l++;
int x = q[l]; assert(x<i);
where[j][i] = x;
dp[1][i] = dp[0][x] + (pre[n]-pre[i])*(pre[i]-pre[x]);
assert(r < N);
k[r] = -pre[i];
b[r] = dp[0][i];
while(r-l > 1 && check2(q[r-2],q[r-1],i))r--;
q[r] = i;
k[r] = -pre[i];
b[r] = dp[0][i];
r++;
}
//cout << endl;
for(int i = 1; i <= n; i++) dp[0][i] = dp[1][i], dp[1][i] = 0;//, cout << dp[0][i] << " "; cout << endl;
}
int ind = 0;
int mx = -1;
/*for(int i = 1; i <= n; i++){
if(dp[0][i] > mx){
mx = dp[0][i];
ind = i;
}
}*/
ind = n;
cout << dp[0][ind] << endl;
int a = cnt+1;
while(a>1){
ind = where[a][ind];
assert(ind < N);
cout << ind << " ";
if(ind == 0){
cout << a << endl;
}
assert(ind);
a--;
}
}
main(){
ios::sync_with_stdio(0);
int T = 1;
//cin >> T;
while(T--){
test_case();
}
}
