#include <bits/stdc++.h>
#define ll long long
#define X first
#define Y second
#define MP make_pair
using namespace std;
const int N = 1e5 + 12;
int n, k, T, IT;
int gr[220][N];
ll pr[N], dp[2][N];
void rec(int tl, int tr, int tpl = 1, int tpr = n){
if(tl > tr)
return;
int tm = (tl + tr) / 2, tp = 0;
ll curs = -1;
for(int i = max(tpl, IT - 1);i <= min(tm - 1, tpr);i++){
if(dp[1 - T][i] + pr[i] * (pr[tm] - pr[i]) > curs)
curs = dp[1 - T][i] + pr[i] * (pr[tm] - pr[i]), tp = i;
}
dp[T][tm] = curs, gr[IT][tm] = tp;
rec(tl, tm - 1, tpl, tp);
rec(tm + 1, tr, tp, tpr);
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for(int i = 1;i <= n;i++){
cin >> pr[i];
pr[i] += pr[i - 1];
}
k += 1;
for(int i = 2;i <= k;i++){
T = i & 1, IT = i;
rec(1, n);
}
cout << dp[k & 1][n] << "\n";
for(int j = k, pos = n;j > 1;j--){
cout << gr[j][pos] << " ";
pos = gr[j][pos];
}
}
