#include <iostream>
#include <cassert>
using namespace std;
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int N = 1e5 + 5, K = 205;
int64_t f[K][N], a[N];
int opt[K][N], st[N];
void solve(int k, int l, int r, int optl, int optr) {
if (r < l) return;
int i = (l + r) / 2;
f[k][i] = -1e18;
for (int j = optl; j <= min(i, optr); ++j)
if (ckmax(f[k][i], f[k - 1][j] + a[j] * (a[i] - a[j])))
opt[k][i] = j;
solve(k, l, i - 1, optl, opt[k][i]);
solve(k, i + 1, r, opt[k][i], optr);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k; cin >> n >> k;
for (int i = 1; i <= n; ++i)
cin >> a[i], a[i] += a[i - 1], f[i][0] = -1e18;
for (int l = 1; l <= k; ++l)
solve(l, l, n, l, n);
// for (int l = 1; l <= k; ++l)
// for (int i = l; i <= k; ++i)
// assert(opt[l][i] > 0);
for (int v = n, l = k; 0 <= l && (v = opt[l--][v]); ) st[l] = v;
cout << f[k][n] << '\n';
for (int l = 0; l < k; ++l) cout << st[l] << ' ';
}
