#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, k;
vector<int> ps;
vector<vector<int>> dp;
vector<vector<signed>> best;
void compute(int l, int r, int optl, int optr, int kl){
if (l > r) return;
int m = (l+r)/2;
pair<int,int> res = {-pow(10, 18), -1};
for (int j=max(m+1, optl); j<=optr; j++){
int cur = dp[1][j]+(ps[j]-ps[m])*(ps[n]-ps[j]);
if (cur >= res.first) res = {cur, j};
}
dp[0][m] = res.first;
best[kl][m] = res.second;
int opt = res.second;
compute(l, m-1, optl, opt, kl);
compute(m+1, r, opt, optr, kl);
}
int solve(){
for (int i=0; i<n; i++) dp[1][i] = 0;
for (int i=1; i<=k; i++){
compute(0, n-1, 0, n-1, i);
dp[1] = dp[0];
}
return dp[0][0];
}
signed main(){
cin.tie(0);
iostream::sync_with_stdio(false);
cin >> n >> k;
ps.resize(n+1, 0);
for (int i=0; i<n; i++){
cin >> ps[i+1];
ps[i+1] += ps[i];
}
dp.resize(2, vector<int>(n, -pow(10, 18)));
best.resize(k+1, vector<signed>(n));
cout << solve() << endl;
int bruh = 0;
for (int i=k; i>0; i--){
cout << best[i][bruh] << " ";
bruh = best[i][bruh];
}
cout << endl;
}
//dp[i][k] = max(dp[j][k-1]+(ps[j]-ps[i])*(ps[n]-ps[j]))
//ps[j]*ps[n]-ps[j]**2-ps[i]*ps[n]+ps[j]*ps[i]
