/*
author : sh1ft
created : 12/07/2025 21:39
task : APIO14_sequence
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mxN = 1e5+5, mxK = 200;
int n, k;
ll p[mxN], dp[mxK][mxN], par[mxK][mxN], q[mxK], mcm[mxK][mxK];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> p[i], p[i] += p[i-1];
for (int i = 1; i <= n; i++) dp[0][i] = p[i];
for (int c = 1; c <= k; c++) {
deque <int> cht; int sz = 0;
cht.emplace_back(c), sz++;
auto calc = [&] (int j, ll x) { return dp[c-1][j]*x - dp[c-1][j]*p[j]; };
auto m = [&] (int x, int y) { return (double) (calc(x, 0) - calc(y, 0)) / (dp[c-1][y] - dp[c-1][x]); };
for (int i = c+1; i <= n; i++) {
while (sz > 1 && calc(cht[0], p[i]) <= calc(cht[1], p[i])) cht.pop_front(), sz--;
par[c][i] = cht[0];
dp[c][i] = calc(cht[0], p[i]);
while (sz > 1 && m(cht[sz-1], i) <= m(cht[sz-1], cht[sz-2])) cht.pop_back(), sz--;
cht.emplace_back(i), sz++;
}
}
vector <int> ct(k);
int id = n;
for (int i = k; i > 0; i--) id = par[i][id], ct[i-1] = id;
ct.emplace_back(n), k++;
for (int i = 1; i <= k; i++) q[i] = p[ct[i-1]];
for (int l = 1; l+1 <= k; l++) {
for (int i = 1; i+l <= k; i++) {
int j = i+l;
for (int x = i; x < j; x++) mcm[i][j] = max(mcm[i][j], mcm[i][x] + mcm[x+1][j] + (q[x] - q[i-1])*(q[j] - q[x]));
}
}
cout << mcm[1][k] << '\n';
for (int i = 0; i < k-1; i++) cout << ct[i] << ' '; cout << '\n';
}
/*
dp[c][i] = max(dp[c-1][j] * (p[i] - p[j]))
= max(dp[c-1][j](p[i]) - dp[c-1][j]*p[j])
*/
