#include "bits/stdc++.h"
using namespace std;
const int maxn = 100005;
using ll = long long;
ll dp[maxn][2];
int n, k;
ll a[maxn], pref[maxn];
int best[maxn][202];
int cur, cnt;
void compute(int l, int r, int optl, int optr){
if(l > r)return;
int mid = (l + r) >> 1;
int opt = optl;
for(int i = optl; i <= min(mid - 1, optr); ++i){
ll cost = dp[i][cur ^ 1] + pref[i] * (pref[mid] - pref[i]);
if(dp[mid][cur] < cost){
dp[mid][cur] = cost;
opt = i;
}
}
best[mid][cnt] = opt;
compute(l, mid - 1, optl, opt);
compute(mid + 1, r, opt, optr);
}
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
for(int i = 1; i <= n; ++i){
pref[i] = pref[i - 1] + a[i];
}
for(int i = 1; i <= k; ++i){
cur = i & 1;
cnt = i;
for(int i = 0; i <= n; ++i){
dp[i][cur] = -1;
}
compute(1, n, 1, n);
}
cout << dp[n][k & 1] << '\n';
cur = n;
int cur_k = k;
while(cur_k > 0){
cout << best[cur][cur_k] << ' ';
cur = best[cur][cur_k];
--cur_k;
}
return 0;
}
