#include <bits/stdc++.h>
#define int long long
#define emb emplace_back
#define pii pair <int, int>
using namespace std;
const int mod = 1e9 + 7;
const int inf = 1e18;
int LR = 5e12 + 5;
const int N = 1e5 + 5;
const int K = 2e2 + 5;
int n, k, a[N], pref[N], dp[2][N], pos[K][N];
struct line {
int m, c;
line(int m, int c) : m(m), c(c) {}
int cal(int x){
return m * x + c;
}
};
struct lichaotree {
struct node {
line val;
int idx;
node *l, *r;
node(line val, int idx) : val(val), idx(idx), l(0), r(0) {}
};
typedef node* pnode;
pnode root;
void update(int l, int r, pnode &i, line cur, int idx){
if (!i) return i = new node(cur, idx), void();
int mid = (l + r) / 2;
if (cur.cal(mid) > i->val.cal(mid)) swap(cur, i->val), swap(i->idx, idx);
if (cur.cal(l) > i->val.cal(l)) update(l, mid, i->l, cur, idx);
if (cur.cal(r) > i->val.cal(r)) update(mid + 1, r, i->r, cur, idx);
}
pii query(int l, int r, pnode &i, int x){
if (!i) return {0, 0};
int mid = (l + r) / 2;
if (x <= mid) return max(make_pair(i->val.cal(x), i->idx), query(l, mid, i->l, x));
else return max(make_pair(i->val.cal(x), i->idx), query(mid + 1, r, i->r, x));
}
} lct;
signed main(){
cin.tie(NULL)->sync_with_stdio(false);
cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i], pref[i] = pref[i - 1] + a[i];
LR = pref[n] * 2;
for (int i = 1; i <= n; i++) dp[0][i] = -inf;
for (int i = 1; i <= k; i++) dp[i%2][0] = -inf;
for (int i = 1; i <= k; i++) {
lct.root = 0;
lct.update(-LR, LR, lct.root, line(-pref[0], dp[(i - 1) % 2][0]), 0);
for (int j = 1; j < n; j++) {
pii curr = lct.query(-LR, LR, lct.root, pref[n] - pref[j]);
curr.first += pref[j] * pref[n] - pref[j] * pref[j];
dp[i % 2][j] = curr.first;
pos[i][j] = curr.second;
lct.update(-LR, LR, lct.root, line(-pref[j], dp[(i - 1) % 2][j]), j);
// cout << i << ", " << j << " : " << dp[i][j] << ", " << pos[i][j] << "\n";
}
}
int ans = -inf, idx = 0, curk = k;
for (int i = 1; i < n; i++) {
if (dp[k % 2][i] >= ans) ans = dp[k % 2][i], idx = i;
}
cout << ans << "\n";
if (ans == 0) {
for (int i = 1; i <= k; i++) cout << i << " ";
}
else {
while (curk > 0) {
cout << idx << " ";
idx = pos[curk--][idx];
}
}
}
/*
*ORDER OF SPLIT DOESN'T MATTER*
dp[i][j] = max score after splitting i'th round at after position j
dp[i][j] = max(dp[i - 1][k] + (pref[j] - pref[k]) * (pref[n] - pref[j]))
dp[i][j] = max(dp[i - 1][k] + pref[j] * pref[n] - pref[j]^2 - pref[k] * pref[n] + pref[k] * pref[j])
dp[i][j] = pref[j] * pref[n] - pref[j]^2 + max(dp[i - 1][k] - pref[k] * (pref[n] - pref[j]))
const = pref[j] * pref[n] - pref[j]^2
m = -pref[k]
x = pref[n] - pref[j]
c = dp[i - 1][k]
*/
