#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif
const int K = 202;
const int N = 1e5 + 5;
const int M = 1e9 + 9;
struct Line {
int m, b, o;
Line() {}
Line(int m_, int b_, int o_) : m(m_), b(b_), o(o_) {}
long long val(int x) {
return (long long) -m * x + b;
}
};
int a[N];
int path[N][K];
long long dp[N][K];
int pref[N], suf[N];
struct LiChaoTree {
int n;
int rt, idd;
vector<Line> seg;
vector<int> L, R;
LiChaoTree(int n_) : n(n_) {
idd = 0;
seg.resize(n);
L.resize(n);
R.resize(n);
}
void upd(int& nd, int l, int r, Line line) {
if (!nd) {
nd = ++idd;
seg[nd] = line;
return;
}
int mid = (l + r) >> 1;
bool f1 = line.val(l) > seg[nd].val(l);
bool f2 = line.val(mid) > seg[nd].val(mid);
if (f2) {
swap(seg[nd], line);
}
if (l == r) {
return;
}
if (f1 != f2) {
upd(L[nd], l, mid, line);
} else {
upd(R[nd], mid + 1, r, line);
}
}
void upd(Line line) {
upd(rt, 0, M, line);
}
pair<long long, int> qry(int nd, int l, int r, int x) {
pair<long long, int> ret = {seg[nd].val(x), seg[nd].o};
//deb(x) deb(ret) cout << '\n';
if (l == r) {
return ret;
}
int mid = (l + r) >> 1;
if (x <= mid) {
ret = max(ret, qry(L[nd], l, mid, x));
} else {
ret = max(ret, qry(R[nd], mid + 1, r, x));
}
return ret;
}
pair<long long, int> qry(int x) {
return qry(rt, 0, M, x);
}
};
int 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];
}
for (int i = 1; i <= n; ++i) {
pref[i] = pref[i - 1] + a[i];
}
for (int i = n; i >= 1; --i) {
suf[i] = suf[i + 1] + a[i];
}
int ind = 0;
long long ans = 0;
for (int i = 1; i <= n; ++i) {
dp[i][k - 1] = (long long) pref[i] * suf[i + 1];
if (k == 1 && dp[i][k - 1] > ans) {
ans = dp[i][k - 1];
ind = i;
}
}
for (int j = k - 2; j >= 0; --j) {
LiChaoTree st(N);
for (int i = k - j; i < n; ++i) {
st.upd(Line(pref[i - 1], dp[i - 1][j + 1], i - 1));
long long c = (long long) suf[i + 1] * pref[i];
auto [cl, l] = st.qry(suf[i + 1]);
dp[i][j] = c + cl;
path[i][j] = l;
if (j == 0 && dp[i][j] > ans) {
ans = dp[i][j];
ind = i;
}
}
}
int cnt = 0;
vector<int> p;
while (ind) {
p.push_back(ind);
ind = path[ind][cnt++];
}
assert(cnt == k);
reverse(p.begin(), p.end());
cout << ans << '\n';
for (int i : p) {
cout << i << ' ';
}
return 0;
}
