#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
int n, k;
vector < long long > pr, a;
vector < vector < int > > par;
vector < vector < long long > > dp;
long long get(int l, int r){
return (pr[r] - pr[l]) * (pr[n] - pr[r]);
}
void f(int k, int l, int r, int optl, int optr){
if(l > r)return;
int mid = (l + r) >> 1;
pair < long long , int > best = {-INF, -1};
for(int i = optl; i <= min(mid - 1, optr); i++){
long long cost = dp[i][k - 1] + get(i, mid);
best = max(best, {cost, i});
}
dp[mid][k] = best.first;
int opt = best.second;
par[mid][k] = opt;
f(k, l, mid - 1, optl, opt);
f(k, mid + 1, r, opt, optr);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
a.assign(n + 1, 0ll);
pr.assign(n + 1, 0ll);
par.assign(n + 1, vector < int > (k + 1, 0));
dp.assign(n + 1, vector < long long > (k + 1, -INF));
for(int i = 1; i <= n; i++){
cin >> a[i];
pr[i] = pr[i - 1] + a[i];
}
dp[0][0] = 0;
for(int i = 1; i <= k; i++)
f(i, 1, n, 0, n - 1);
long long mx = -INF, id = -1;
for(int i = 1; i <= n; i++){
if(mx < dp[i][k]){
mx = dp[i][k];
id = i;
}
}
cout << mx << "\n";
set < int > ans;
while(id != 0){
ans.insert(id);
id = par[id][k--];
}
for(int i : ans)
cout << i << ' ';
}
